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

Time Limit: 2 Seconds      Memory Limit: 65536 KB

The bored Bob is playing a number game. In the beginning, there are n numbers. For each turn, Bob will take out two numbers from the remaining numbers, and get the product of them. There is a condition that the sum of two numbers must be not larger than k.

Now, Bob is curious to know what the maximum sum of products he can get, if he plays at most m turns. Can you tell him?

Input

The first line of input contains a positive integer T, the number of test cases. For each test case, the first line is three integers n, m(0≤ n, m ≤100000) and k(0≤ k ≤20000). In the second line, there are n numbers ai(0≤ ai ≤10000, 1≤ in).

Output

For each test case, output the maximum sum of products Bob can get.

Sample Input

2
4 2 7
1 3 2 4
3 2 3
2 3 1

Sample Output

14
2

Author: XIAN, Weizhao
Source: ZOJ Monthly, October 2015
Submit    Status