Easy Number Game

Time Limit: 2 Seconds

Memory Limit: 65536 KB

Description

The bored BaoBao is playing a number game. In the beginning, there are \(n\) numbers. For each turn, BaoBao will take out two numbers from the remaining numbers, and calculate the product of them.

Now, BaoBao is curious to know the minimum sum of the products if he plays at least \(m\) turns. Can you tell him?

Input

The first line of input contains a positive integer \(T\) (about 30), the number of test cases. For each test case:

The first line contains two integers \(n\) and \(m\) (\(1 \le n \le 10^5\), \(0 \le m \le \frac{n}{2}\)). Their meanings are described above.

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) (\(0 \le a_i \le 10^4\)), indicating the numbers.

Output

For each test case output one integer, indicating the minimum sum of the products.

Sample Input

3
4 2
1 3 2 4
3 1
2 3 1
4 0
1 3 2 4

Sample Output

10
2
0

Hint

For the first sample test case, the answer is 1 × 4 + 3 × 2 = 10.

For the second sample test case, the answer is 2 × 1 = 2.

Source

None

提交代码