Boring Number Game

Time Limit: 5 Seconds    Memory Limit: 65536 KB

Amir bored and he’s trying to play a number game. In the beginning, there are n numbers. At each turn, Amir takes out two numbers from the remaining numbers, and calculate the product of them.

Now, Amir is curious to know the minimum sum of those products if he plays at least m turns.

Input

The first line of input contains a positive integer T ≤ 32, the number of test cases. For each test case, the first line contains the two integers n and m (1 ≤ n ≤ 105, 0 ≤ m ≤ n/2).

The second line contains n integers a1, a2, …, an (0 ≤ ai ≤ 104), 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

Submit