D. Skibidus and Sigma
greedy; sortings
Let's denote the score of an array \(b\) with \(k\) elements as \(\sum_{i=1}^{k}\left(\sum_{j=1}^ib_j\right)\). In other words, let \(S_i\) denote the sum of the first \(i\) elements of \(b\). Then, the score can be denoted as \(S_1+S_2+\ldots+S_k\).Skibidus is given \(n\) arrays \(a_1,a_2,\ldots,a_n\), each of which contains \(m\) elements. Being the sigma that he is, he would like to concatenate them in any order to form a single array containing \(n\cdot m\) elements. Please find the maximum possible score Skibidus can achieve with his concatenated array! Formally, among all possible permutations\(^{\text{∗}}\) \(p\) of length \(n\), output the maximum score of \(a_{p_1} + a_{p_2} + \dots + a_{p_n}\), where \(+\) represents concatenation\(^{\text{†}}\).\(^{\text{∗}}\)A permutation of length \(n\) contains all integers from \(1\) to \(n\) exactly once.\(^{\text{†}}\)The concatenation of two arrays \(c\) and \(d\) with lengths \(e\) and \(f\) respectively (i.e. \(c + d\)) is \(c_1, c_2, \ldots, c_e, d_1, d_2, \ldots d_f\).
The first line contains an integer \(t\) (\(1 \leq t \leq 10^4\)) — the number of test cases.The first line of each test case contains two integers \(n\) and \(m\) (\(1 \leq n \cdot m \leq 2 \cdot 10^5\)) — the number of arrays and the length of each array.The \(i\)'th of the next \(n\) lines contains \(m\) integers \(a_{i,1}, a_{i,2}, \ldots, a_{i,m}\) (\(1 \leq a_{i,j} \leq 10^6\)) — the elements of the \(i\)'th array.It is guaranteed that the sum of \(n \cdot m\) over all test cases does not exceed \(2 \cdot 10^5\).
For each test case, output the maximum score among all possible permutations \(p\) on a new line.
For the first test case, there are two possibilities for \(p\): \(p = [1, 2]\). Then, \(a_{p_1} + a_{p_2} = [4, 4, 6, 1]\). Its score is \(4+(4+4)+(4+4+6)+(4+4+6+1)=41\). \(p = [2, 1]\). Then, \(a_{p_1} + a_{p_2} = [6, 1, 4, 4]\). Its score is \(6+(6+1)+(6+1+4)+(6+1+4+4)=39\). The maximum possible score is \(41\).In the second test case, one optimal arrangement of the final concatenated array is \([4,1,2,1,2,2,2,2,3,2,1,2]\). We can calculate that the score is \(162\).