U265607 收集数字（number）

一年的工作结束了，现在是绝佳的休假时间，当然也是非常适合整理物品的。在翻看数年前的照片时，Blue_balloon 忽然注意到了 NumbersCollector —— 这是一个被用于开发儿童智力的经典游戏。游戏的规则是这样的： \ \ \ **·** 首先，电脑会生成一个 $n$ 行 $m$ 列的矩形棋盘，这个棋盘中总共有 $n \times m$ 个方格，其中位于第 $i$ 行第 $j$ 列的方格的坐标为 $(i,j)$. 左上角方格的坐标为 $(1,1)$，右下角方格的坐标为 $(n,m)$. **·** 在这之后，电脑会在棋盘的每个方格中填入一个整数（不一定是正整数），具体来说，它会在坐标为 $(i,j)$ 的方格处填入数字 $a_{i,j}$ . **·** 数字全部填完之后，玩家操控的小熊会出现在棋盘中，它的初始坐标为 $(1,1)$. 当小熊位于方格 $(x,y)$ 时，玩家可以操控它前往 $(x,y+1)\, , (x+1,y)\, ,(x+1,y+1)$ 三个位置之一（前提是小熊将要到达的位置不超过棋盘的范围）。也就是说，小熊每次都可以向 **右方、下方或右下方** 行走一步，但必须保证它 **任何时刻都位于棋盘的某个方格上**。 **·** 当小熊到达方格 $(n,m)$ 时，游戏结束。此时，玩家的得分为 **小熊经过的所有方格上数字的总和**（包括起点和终点）。玩家需要尽可能使这个得分最大化。 \ \ \ 除此之外，Blue_balloon **在小熊出现之前** 还可以使用一种游戏道具 —— **数字炸弹**：这种道具的使用方法是先选择棋盘的 **某一行或某一列** 作为爆炸范围，之后只要投掷一颗数字炸弹，就可以将爆炸范围内所有方格上的数改为其相反数（也就是乘上 $-1$）。 这个游戏总共有 $T$ 关。针对这些关卡，Blue_balloon 总共可以使用 **至多** $\bm{k}$ **颗** 数字炸弹，他需要把这 $k$ 次使用机会以某种方式分配给 $T$ 个关卡（所有关卡使用的数字炸弹数量的总和 $\sum b$ 应当满足 $\sum b \le k$），从而最大化他在所有关卡中得分的总和。 理想很丰满，现实很骨感。这不是一个困难的任务，但 Blue_balloon 实在太菜了，因此请你告诉他，他在 $T$ 个关卡中的得分总和的最大值是多少。

第一行包含一个正整数 $T$ 和一个非负整数 $k$，用空格隔开，分别表示关卡的个数和数字炸弹使用次数的上限。 接下来会输入 $T$ 组数据（每两组数据间没有空行），依次表示每个关卡的棋盘状态。对于第 $t$ 组数据而言： 第一行包含两个正整数 $n,m$，用空格隔开，分别表示第 $t$ 关中棋盘的行数和列数。 接下来 $n$ 行，每行包含 $m$ 个整数，用空格隔开，其中第 $i$ 行的第 $j$ 个整数表示方格 $(i,j)$ 中填入的数字 $a_{i,j}$.

仅需输出一个整数，表示 Blue_balloon 在 $T$ 个关卡中的得分总和的最大值。

| 测试点编号 | $T \leq$ |$n,m \le$ | $k \le$ | $\mid a_{i,j} \mid \, \le$ | 特殊性质 | |:-:|:-:|:-:|:-:|:-:|:-:| | $1 \sim 2$ | $1$ | $10$ | $0$ | $10$ | / | $3 \sim 4$ | $2$ | $10$ | $15$ | $10$ | / | $5 \sim 6$ | $10$ | $100$ | $150$ | $10^4$ | A | $7$ | $10$ | $100$ | $150$ | $10^4$ | B | $8 \sim 10$ | $10$ | $100$ | $150$ | $10^9$ | / 更严谨地说，表格中的 $n\, ,m$ 表示 $T$ 个关卡中 $n$ 和 $m$ 的较大者的最大值；$\mid a_{i,j}\mid$ 表示 $T$ 个关卡中的所有方格上所填数字的绝对值的最大值。 特殊性质 A：对于所有的 $T$ 个棋盘，$n=1$ 特殊性质 B：$k \ge \sum n+ \sum m$ ，其中 $\sum n , \sum m$ 分别表示所有的 $T$ 个关卡中 $n$ 与 $m$ 的总和。 为避免对算法复杂度的常系数的考察，本题的时间限制被设为 2.00s，内存限制被设为 256.00 MB，均为平常的两倍。 \ \ 样例 #4 / #5 / #6 的数据范围及特殊性质分别与测试点 $5 \sim 6$ / $7$ / $8 \sim 10$ 相同。 \ \ \ 【样例 #1 解释】 该样例下无法使用数字炸弹。可以看出，直接从 $(1,1)$ 前往右下方并到达 $(2,2)$，能获得最大得分 $0$.\ \ \ 【样例 #2 解释】 该样例下所有方格中的数字都是正数，因此，无论在何处使用数字炸弹，都不会使得任何数字的值增加。在不使用数字炸弹的基础上，从起点开始先水平向右移动到棋盘的最后一列，再竖直向下移动到终点是一种最优策略。 \ \ \ 【样例 #3 解释】 可以发现，最优策略是在第一关使用 $3$ 颗数字炸弹，而后在第二关使用 $1$ 颗数字炸弹（直接对唯一的一行方格使用数字炸弹，之后不断向右走到终点即可）。对于第一关来说，Blue_balloon 应当对第 $2$ 行、第 $4$ 行、第 $3$ 列分别使用数字炸弹，此时棋盘中所有方格上填写的数字如下表所示： | 行/列 | 1 | 2 | 3 | 4 | 5 | 6 | |:-:|:-:|:-:|:-:|:-:|:-:|:-:| | **1** | $\color{orange}1$ | $\color{orange}2$ | $\color{orange}3$ | $-4$ | $5$ | $6$ | | **2** | $-1$ | $1$ | $\color{orange}4$ | $\color{orange}5$ | $-1$ | $4$ | | **3** | $2$ | $3$ | $-3$ | $\color{orange}3$ | $\color{orange}3$ | $\color{orange}3$ | | **4** | $-2$ | $3$ | $-3$ | $3$ | $3$ | $\color{orange}3$ | | **5** | $6$ | $-5$ | $4$ | $-3$ | $-2$ | $\color{orange}-1$ | 容易看出，依次经过方格 $(1,1)\, ,(1,2)\, ,(1,3)\, ,(2,3)\, ,(2,4)\, ,(3,4)\, ,(3,5)\, ,(3,6)\, ,(4,6)\, ,(5,6)$ 能产生得分 $1+2+3+4+5+3+3+3+3-1=26$，再加上第二关的得分 $1+1+4+5+1+4=16$ ，总得分为 $42$ ，可以证明为最大总得分。 \ \ \ 为了更全面地检验算法的正确性，您可以参考以下内容。 对于样例 #3 来说，在其它输入数据不变的情况下，答案随 $k$ 的部分取值的变化情况如下： | $\bm{k}=$ | 标准输出 | |:-:|:-:| | $0$ | $-1$ | $1$ | $31$ | $2$ | $37$ | $3$ | $41$ | $4$ | $42$ | $5$ | $46$ | $6$ | $48$ | $7$ | $48$ | $8$ | $48$