题目内容

给定一个$n \times m$ 的整数矩阵$A$。你需要进行两次操作：每次选择一行或一列，将所选行（或列）上的所有元素取走并累加到总和中。被取走后，该行（或该列）上所有被选择到的元素的值立即变为 $0$，在后续操作中按 $0$ 计。求能够获得的最大总和。

更形式化地，设两次操作依次选择的线为$L_1, L_2$。

• 第一次操作的收益为$L_1$上元素之和；
• 将$L_1$上元素全部置为$0$后，第二次操作的收益为此时$L_2$ 上元素之和；
• 答案为两次收益之和。

输入描述

输入包含多组测试数据。

• 第一行包含整数 $T\ (1 \le T \le 10^5)$表示测试组数。
• 每组数据描述如下：
  1. 第一行包含两个整数 $n, m\ (1 \le n, m,\ n \times m \le 2 \times 10^5)$；
  2. 接下来$n$行，每行包含 $m$ 个整数，表示矩阵 A 的元素 $A_{i,j}\ (-10^9 \le A_{i,j} \le 10^9)$。
• 保证所有测试中 $n \times m$的总和不超过 $5 \times 10^5$。

输出描述

对于每组测试数据，输出一行一个整数，表示进行两次操作可以获得的最大总和。

样例1

输入

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

输出

39
26
9

说明

• 样例一：选择第 $2$行与第 $3$行，总和为$15 + 24 = 39$，为最优。
• 样例二：第一次选择第 $2$ 行，收益为 $10 + 1 + 5 = 16$；将该行置零后再选择第$2$ 列，此时该列仅剩 $(1,2)$位置的 $10$，收益 $10$。合计 $16 + 10 = 26$。
• 样例三：仅选择第一列和第三列，总和为 $5 + 4 = 9$。