D. Skibidus 和 Sigma

https://codeforces.com/problemset/problem/2065/D

我们将一个长度为 \(k\) 的数组 \(b\) 的得分定义为：

\( \text{score}(b) = \sum_{i=1}^{k} \left( \sum_{j=1}^{i} b_j \right) \)

换句话说，令 \(S_i\) 表示数组 \(b\) 的前 \(i\) 项和：

\( S_i = \sum_{j=1}^{i} b_j \)

那么得分即为：

\( S_1 + S_2 + \cdots + S_k \)

Skibidus 拿到了 \(n\) 个数组 \(a_1, a_2, \dots, a_n\)，每个数组长度为 \(m\)。
作为一个"Sigma"，他希望将这 \(n\) 个数组以任意顺序拼接成一个总长度为 \(n \cdot m\) 的数组，
使得拼接后的整体得分最大。

更正式地说：

在所有长度为 \(n\) 的排列 \(p\) 中，输出拼接数组 \(a_{p_1} + a_{p_2} + \cdots + a_{p_n}\) 的最大得分。

这里的 \(+\) 表示数组拼接操作。

拼接定义

若数组 \(c = [c_1, c_2, \dots, c_e]\)，数组 \(d = [d_1, d_2, \dots, d_f]\)，
则拼接 \(c + d\) 的结果为：

\( [c_1, c_2, \dots, c_e, d_1, d_2, \dots, d_f] \)

输入格式

• 第一行一个整数 \(t\)（\(1 \le t \le 10^4\)）——测试用例数量。

对于每个测试用例：

• 第一行两个整数 \(n\) 和 \(m\)（\(1 \le n \cdot m \le 2 \times 10^5\)）——数组数量与每个数组长度；
• 接下来的 \(n\) 行中，每行包含 \(m\) 个整数 \(a_{i,1}, a_{i,2}, \dots, a_{i,m}\)（\(1 \le a_{i,j} \le 10^6\)），表示第 \(i\) 个数组的内容。

保证所有测试用例中 \(n \cdot m\) 的总和不超过 \(2 \times 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

样例解释

样例 1：

有两种拼接顺序：

1. \(p = [1, 2]\)，拼接得到数组 \([4, 4, 6, 1]\)

其前缀和分别为：

\( S_1 = 4,\quad S_2 = 4 + 4 = 8,\quad S_3 = 4 + 4 + 6 = 14,\quad S_4 = 4 + 4 + 6 + 1 = 15 \)

得分为：

\( 4 + 8 + 14 + 15 = 41 \)

1. \(p = [2, 1]\)，拼接得到数组 \([6, 1, 4, 4]\)

前缀和为：

\( S_1 = 6,\quad S_2 = 7,\quad S_3 = 11,\quad S_4 = 15 \)

得分为：

\( 6 + 7 + 11 + 15 = 39 \)

最大得分为 \(41\)。