H. Minimise Cost
time limit per test
6 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

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.

Example
Input
6
3 2
1 3 -2
3 1
1 3 -2
10 4
-4 -6 -8 6 -3 -7 -3 1 6 -5
10 9
1 -2 6 -2 -6 4 3 3 7 -1
20 5
-5 9 -4 10 -2 4 -1 3 5 6 7 9 8 1 0 -6 4 5 8 9
50 26
7 10 10 2 2 1 7 4 4 8 5 8 -10 6 1 4 7 8 0 0 -8 1 1 5 0 0 6 0 7 4 6 0 7 4 -2 0 0 8 1 4 -7 0 6 -9 4 10 8 2 0 9
Output
1
6
-239
5
131
-404
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$$$.