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{†}}$.

Input

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$.

Output

For each test case, output the maximum score among all possible permutations $p$ on a new line.

见题面 Input 部分

见题面 Output 部分

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$.