题目内容

小蓝获得了一个大小为 $r \times c$ 的整数矩阵，她可以依次执行两次采集操作。每次操作需要选择矩阵中的一整行或一整列，获取该行（或列）里所有当前数值的总和，并立即将所选行（或列）中的所有元素置为 $0$。两次操作按顺序执行，第一次操作完成后才能进行第二次操作。小蓝希望最大化两次操作所得数值的总和，请你帮助她计算这个最大总和。

数据约束：测试用例的组数不超过 100000。每组数据中，矩阵的行数 $r$ 和列数 $c$ 满足 $1 \le r, c$，且 $r \times c \le 200000$。矩阵中每个整数的绝对值不超过 $10^9$。所有测试用例的矩阵元素总数不超过 $500000$。

输入描述

第一行包含一个整数 q，表示测试用例的组数。接下来每组测试用例的格式如下：第一行包含两个整数 r 和 c，依次表示矩阵的行数和列数；接下来 r 行，每行包含 c 个整数，表示矩阵中的元素。

输出描述

对于每组测试用例，输出一行一个整数，表示两次采集操作能获得的最大总收益。

样例1

输入

2
1 1
5
2 2
-1 -1
-1 10

输出

5
9

说明

第一组测试用例中，矩阵为 $1 \times 1$，元素为 5。第一次操作采集该行或列，收益 5；第二次操作可以再次选择已清零的同一行或列，收益 0，总收益为 5。

第二组测试用例中，矩阵包含负数，行和分别为 -2 与 9，列和也分别为 -2 与 9。最优策略是先选第二行（收益 9），第二次再选同一行（收益 0），总收益 9。若尝试一行加一列（例如第二行与第二列），收益为 $9 + 9 - 10 = 8$，不如两次选同一行的策略。

样例2

输入

1
3 3
1 2 3
4 5 6
7 8 9

输出

39

说明

矩阵行和依次为 $6, 15, 24$，列和依次为 $12, 15, 18$。

• 两次都选行：取最大的两个行和 $24 + 15 = 39$。
• 两次都选列：取最大的两个列和 $18 + 15 = 33$。
• 一行加一列：最优组合为第三行与第三列，收益 $24 + 18 - 9 = 33$。 因此最大总收益为 39。

样例3

输入

1
2 3
5 -10 5
-10 20 -10

输出

20

说明

第一行和为 $5 + (-10) + 5 = 0$，第二行和为 $(-10) + 20 + (-10) = 0$；第一列和 $-5$，第二列和 $10$，第三列和 $-5$。

• 两次都选行总收益为 0。
• 两次都选列，取最大两列和 $10 + (-5) = 5$。
• 一行加一列：选第一行（和 $0$）与第二列（和 $10$），交点处元素为 $-10$，收益为 $0 + 10 - (-10) = 20$。 因此最大总收益为 20。