Weird Deal

Time Limit: 5 Seconds    Memory Limit: 65536 KB

The “ICPC Careless Packaging Company” (Confused?! it’s recursive!) has been selected to do a weird kind of delivery. A factory asked ICPC to deliver some packages from their storage to the factory. Each package has its own weight and there is a weight limit L for the truck as well. So the total sum of packages’ weight in the truck could not be more than L. On the other hand, ICPC’s trucks have only two compartments each. So each truck could not carry more than two packages at the same time.

The packaging company would charge the factory the multiplication of weights of the packages in each truck. So for delivering two packages with wight of 3 tons and 8 tons in one truck (assuming 8 + 3 = 12 ≤ L), the company charges the factory for 3 × 8 = 24 IRD (Iranian Dollars). The factory would not pay for the deliveries with just one package in the truck as the weight of the other packages would be zero.

According to the government’s laws, ICPC have to send the trucks at the same time and only once for each project. So they load all the trucks they need at the storage and send them to the factory, and that’s the end of the project. They can not reuse a truck in the same project.

In total, ICPC has M trucks, all of them with the same weight limit L. There are N packages in the factory’s storage.

ICPC might not be able to deliver all of the packages, but wants to maximize their profit. Now the task is to compute the maximum profit for the ICPC given the total number of trucks, their weight limit and the weights of each package in the storage.

Input

The input contains several test cases.

In the first line of input comes T (0 < T ≤ 32), the number of test cases.

For each test case the first line comes with three integer N,M,L (0 ≤ N ≤ 10⁵, 0 ≤ M ≤ 10⁵, 0 ≤ L ≤ 2 × 10⁴), indicating the number of packages in the storage, the number of ICPC’s trucks and the weight limit of the trucks respectively.

In the next line there would be N space separated integers pi (0 ≤ pi ≤ 10⁴) indicating the weight of the each packages in the storage.

Output

For each test print the maximum profit of ICPC for efficient delivery of the package.

Sample Input

2
4 2 6
4 1 3 2
4 1 6
2 1 4 5

Sample Output

11
8

Submit

Source: 13th Iran Nationwide Internet Contest - UT