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

Minimise Cost

Examples