题目描述

定义一个 $k$ 个元素的数组 $b$ 的分数为 $\sum_{i=1}^{k}\left(\sum_{j=1}^{i}b_j\right)$，也就是说，设 $S_i$ 表示数组 $b$ 的前 $i$ 个元素之和，则分数可以写作 $S_1 + S_2 + \ldots + S_k$。

Skibidus 得到了 $n$ 个数组 $a_1, a_2, \ldots, a_n$，每个数组包含 $m$ 个元素。作为西格玛男人，他希望能将这 $n$ 个数组按任意顺序拼接成一个包含 $n \cdot m$ 个元素的数组，以使最终得到的拼接数组的分数达到最大。请你帮助他计算拼接后能够获得的最大分数！

形式上地说，在所有可能的长度为 $n$ 的排列 $p$ 中， 求出数组 $a_{p_1} + a_{p_2} + \dots + a_{p_n}$ 的最大分数， 其中符号 $+$ 表示数组拼接。

$^{\text{∗}}$ 一个排列指的是一个包含 $1$ 到 $n$ 的所有整数且每个整数恰好出现一次的序列。
$^{\text{∗}}$ 两个数组 $c$ 和 $d$（长度分别为 $e$ 和 $f$）的拼接 $c+d$ 定义为 $c_1, c_2, \ldots, c_e, d_1, d_2, \ldots, d_f$。

输入格式

第一行包含一个整数 $t$ ($1 \leq t \leq 10^4$)，表示测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $m$ ($1 \leq n \cdot m \leq 2 \cdot 10^5$)，分别表示数组的个数和每个数组的长度。

接下来的 $n$ 行中，第 $i$ 行包含 $m$ 个整数 $a_{i,1}, a_{i,2}, \ldots, a_{i,m}$ ($1 \leq a_{i,j} \leq 10^6$)，表示第 $i$ 个数组的元素。

保证所有测试用例中，$n \cdot m$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一行一个整数，表示所有排列中拼接数组能够获得的最大分数。

样例

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

41
162
72

样例说明

在第一个测试用例中，有可能的两种排列：

• $p = [1, 2]$，拼接后的数组为 $a_{p_1} + a_{p_2} = [4, 4, 6, 1]$，分数为 $4 + (4+4) + (4+4+6) + (4+4+6+1) = 41$。
• $p = [2, 1]$，拼接后的数组为 $a_{p_1} + a_{p_2} = [6, 1, 4, 4]$，分数为 $6 + (6+1) + (6+1+4) + (6+1+4+4) = 39$。

因此，最大可能分数为 $41$。

在第二个测试用例中，一个最优的拼接结果为 $[4,1,2,1,2,2,2,2,3,2,1,2]$，分数为 $162$。

来源

Codeforces 2065D，英文题名 Skibidus and Sigma。