Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 4004
Easy Number Game

Time Limit: 2 Seconds      Memory Limit: 65536 KB

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.


Author: XIAN, Weizhao
Source: ZOJ Monthly, March 2018
Submit    Status