Pak Chanek 有一个朋友在食堂里经营饮料摊。他的朋友将在 $$$n$$$ 天里出售饮料,从 $$$1$$$ 天到 $$$n$$$ 天进行编号。还有$$$m$$$类型的饮料,编号从$$$1$$$到$$$m$$$。
在特定日期销售饮料获得的利润可能会有所不同。在 $$$i$$$ 天,销售 $$$j$$$ 类型饮料的预计利润为 $$$A_{i, j}$$$。请注意,$$$A_{i, j}$$$ 可能为负数,这意味着出售饮料实际上会产生损失。
Pak Chanek 希望帮助他的朋友计划 $$$n$$$ 天内的销售。在 $$$i$$$ 天,Pak Chanek 必须选择出售至少一种饮料。此外,一天销售的饮料类型必须形成一个子数组。换句话说,Pak Chanek 每天都会选择 $$$i$$$ 和 $$$j$$$,使得 $$$1 \leq i \leq j \leq m$$$。那么$$$i$$$到$$$j$$$(含)之间的所有类型的饮料都将被出售。
但为了保证前一天的顾客不断回头,$$$i$$$当天销售的饮品类型选择($$$i>1$$$)必须满足以下条件:
- 在 $$$i$$$ 日销售的至少一种饮料类型还必须在 $$$i-1$$$ 日销售。
- 在 $$$i$$$ 日出售的至少一种饮料类型不得在 $$$i-1$$$ 日出售。
每日利润是当天销售的所有饮料类型的利润总和。销售计划的总利润是 $$$n$$$ 天的利润之和。如果 Pak Chanek 最优地规划销售,可以实现的最大总利润是多少?
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$; $$$3 \leq m \leq 2 \cdot 10^5$$$; $$$n \cdot m \leq 2 \cdot 10^5$$$) - 数字网格中的行和列。
每个测试用例接下来的 $$$n$$$ 行分别包含 $$$m$$$ 个整数,其中第 $$$i$$$ 行包含整数 $$$A_{i,1} A_{i,2}, \ldots, A_{i,m}$$$ ($$$-10^9 \leq A_{i,j} \leq 10^9$$$) — 预测每种饮料类型在第 $$$i$$$ 天的利润。
保证所有测试用例的 $$$n \cdot m$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数:Pak Chanek 可以获得的最大利润。
示例
输入 #1
1 3 6 79 20 49 5 -1000 500 -105 9 109 24 -98 -499 14 47 12 39 23 50
输出 #1
475
注意
这是 Pak Chanek 的最佳计划:
- 在$$$1$$$当天,Pak Chanek 出售饮料类型 $$$1$$$ 到 $$$3$$$。产生利润 $$$79+20+49 = 148$$$。
- 在$$$2$$$当天,Pak Chanek 出售饮料类型 $$$2$$$ 到 $$$4$$$。产生利润 $$$9+109+24 = 142$$$
- 在$$$3$$$当天,Pak Chanek 出售饮料类型 $$$1$$$ 到 $$$6$$$。产生利润 $$$185$$$。
因此,Pak Chanek 计划的总利润为 $$$148 + 142 + 185 = 475$$$。