让我们将具有 $$$k$$$ 元素的数组 $$$b$$$ 的分数表示为 $$$\sum_{i=1}^{k}\left(\sum_{j=1}^ib_j\right)$$$。换句话说,让 $$$S_i$$$ 表示 $$$b$$$ 的前 $$$i$$$ 元素的总和。那么,分数可以表示为$$$S_1+S_2+\ldots+S_k$$$。
Skibidus 被赋予 $$$n$$$ 数组 $$$a_1,a_2,\ldots,a_n$$$,每个数组包含 $$$m$$$ 个元素。作为西格玛,他希望以任意顺序连接它们以形成包含 $$$n\cdot m$$$ 元素的单个数组。请找出斯基比杜斯通过他的串联阵列所能达到的最大得分!
形式上,在长度为$$$n$$$的所有可能的排列$$$^{\text{*}}$$$ $$$p$$$中,输出最大分数$$$a_{p_1} + a_{p_2} + \dots + a_{p_n}$$$,其中$$$+$$$表示串联$$$^{\text{†}}$$$。
输入
第一行包含一个整数 $$$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$$$。
输出
对于每个测试用例,在新行上输出所有可能排列 $$$p$$$ 中的最大分数。
示例
输入 #1
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
输出 #1
41 162 72
注意
对于第一个测试用例,$$$p$$$ 有两种可能性:
- $$$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$$$。