A-矩阵游戏_华中农业大学第十五届程序设计竞赛（新生赛）同步赛

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

给定一个单调不降的序列 $[b_1,b_2,\ldots b_n]$ 与一个 $k$ 行 $n$ 列的矩阵 $A$ 。其中，矩阵 $A$ 的第 $i$ 行第 $j$ 列的元素 $a_{i, j}=b_j$ 。

签到哥希望从矩阵的第 $1$ 行第 $1$ 列移动到第 $k$ 行的任意一列。记 $(x, y)$ 表示签到哥的位置在矩阵的第 $x$ 行第 $y$ 列。当签到哥位于 $(i, j)$ 时，他可以移动到 $(i + 1, j - 1)$ 或 $(i + 1, j)$ 或 $(i + 1, j + 1)$ 。签到哥的位置 $(x, y)$ 需要始终满足 $1 \leq x \leq k$ 且 $1 \leq y \leq n$ 。

签到哥的初始体力为 $b_1$ 。如果签到哥想要移动到 $(x, y)$ ，那么只有当签到哥当前的体力不低于 $a_{x, y}$ 时，签到哥才能移动。移动后，签到哥的体力立即增加 $a_{x , y}$ 。

请求出签到哥到达第 $k$ 行的任意一列后体力的最大值。

一个序列 $c_1, c_2, \ldots, c_n$ 是单调不降的，当且仅当 $c_1 \le c_2 \le \ldots \le c_n$ 。

输入描述:

输入包含多组数据。

首先输入一行一个整数  ()，表示数据的组数。

对于每组数据，首先输入一行两个整数 ,  (, )。

接下来输入一行  个整数  ()。保证  ()。

保证对于一个测试点的所有数据， 的和不超过 。

输出描述:

对于每组数据，输出一行一个整数，表示签到哥到达第  行时体力的最大值。

示例1

输入

复制

3
4 4
1 1 2 3
2 6
1 1 1 4 4 5
5 2
1 2

输出

复制

7
2
8

说明

在第一组数据中，矩阵如下：


签到哥可以选择如下路径：


最终体力值为 。可以证明，这是签到哥体力能达到的最大值。

在第二组数据中，一组最优的路线为 ，最终体力值为 。

在第三组数据中，一组最优的路线为 ，最终体力值为 。