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

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.

Note

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

Skibidus and Sigma

Examples