For any sequence $b$ of length $m$, we define its cost function $f(b)$ as: $$ f(b) = m \cdot \sum_{i=1}^m b_i.$$

You are given a sequence $a$ of length $n$ and an integer $k$.

Your task is to partition the sequence $a$ into exactly $k$ non-empty subsequences$^{\text{∗}}$, denoted as $s_1, s_2, \ldots, s_k$. Every element of the original sequence $a$ must belong to exactly one of these subsequences.

Find the minimum possible value of the total cost: $$ \sum_{i=1}^k f(s_i).$$

$^{\text{∗}}$A sequence $c$ is a subsequence of a sequence $d$ if $c$ can be obtained from $d$ by the deletion of several (possibly, zero or all) element from arbitrary positions.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line contains two integers $n$ and $k$ ($1\le k\le n \le 2\cdot 10^5$) — the length of the sequence and the number of subsequences required.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($\mathbf{-10^9} \le a_i \le \mathbf{10^9}$) — the elements of the sequence $a$.

It is guaranteed that the sum of $n$ across all test cases does not exceed $2\cdot 10^5$.

Output

For each test case, output a single integer – the minimum sum of cost over all subsequences.

Note

In the first test case, it is optimal to split into $[1,-2]$ and $[3]$. The total score is $2(1-2)+1(3)=1$.

In the second test case, the only possible way to partition is with $1$ subsequence $[1,3,-2]$. The score is $3(1+3-2)=6$.