
ZOJ Problem Set  4004
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? InputThe 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. OutputFor each test case output one integer, indicating the minimum sum of the products. Sample Input3 4 2 1 3 2 4 3 1 2 3 1 4 0 1 3 2 4 Sample Output10 2 0 HintFor 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 