Boxes

3.9

8 votes
Problem

You have N chocolates. You want to buy boxes to fill the N chocolates you have. There are boxes from size between 1 to N inclusive available in market. In a box of size S you can keep exactly S chocolates, not more not less. Cost of a box of size i is Pi (1<= i <= N). You will get a concession of X for every bought box. Now you have to buy some boxes to fill the N chocolates you have. All the boxes you have bought should be completely filled with chocolates and no box should be left empty. Also, multiple boxes of the same size can be bought. Find the maximum bill possible.

Input:
First line contains t no of test cases, for each test case first line will contain two space separated integers N and X. Next line will contain N space separated integers Pi

Output:
For each test case output a single line containing the amount of bill.

Constraints:
1<= t <= 50
1 <= N <= 10^3
1 <= X < 100
100 <= Pi <= 500

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

Here we have 3 boxes and 3 chocolates. Possible combinations:
1)3 boxes of size 1
2)2 boxes of size 1 and 1 box of size 2
3)1 box of size 3
To maximize the bill we can use 3 boxes of size 1 costing 300 each, so the bill now is 900,but there is concession of 50 per box, so the final bill becomes 900-(50*3)=750 and that is the maximum possible.

Editor Image

?