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?

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.

提交代码