Sereja and Stones

All submissions for this problem are available.
Sereja has N boxes and M stones. There is a parameter energy associated with each empty box, denoted by E_{i}. He wants to move each stone into some box. After moving all the stones into the boxes, he wants to compute the total energy of box/stone system. For that he believes that a contribution of box into energy of the system can be computed as follows. If box i contains s stones and there are total k boxes out there containing more than s stones, then contribution of box i into the system of energy will be given by E_{i} × k.
Sereja wants the box/stone system to be most stable, i.e. it should have least possible energy. Find out minimum possible energy of this system.
Input
First line of the input contains an integer T denoting the number of test cases. T tests follow.
First line of each test case contains two space separated integers N and M.
Next line contains N space separated integers denoting the array E.
Output
For each test case output a single integer corresponding to the answer of the problem.
Constraints
 1 ≤ T ≤ 7
 7 ≤ N, M ≤ 77777
 7 ≤ E[i] ≤ 77
Subtasks
 Subtask #1: (20 points) 7 ≤ N ≤ 77, 7 ≤ M ≤ 777
 Subtask #2: (30 points) 7 ≤ N, M ≤ 777
 Subtask #3: (50 points) original constraints
Example
Input: 2 2 4 7 8 4 6 7 7 10 10 Output: 0 21
Explanation
In test case 1, there are 2 boxes and 4 stones. The energy of two empty boxes are 7 and 8 respectively. You can put 2 stones into each of the box. Contribution of both the boxes into the energy of the system will be zero. So, the answer will be zero.
In test case 2, there are 4 boxes and 6 stones. You can distribute the stones into boxes as follows, [0, 2, 2, 2]. Contribution of the first box into total energy will be equal to 7 * 3 and that of rest of the boxes will be zero. So, overall energy will be 21. You can enumerate all possible distributions of the stones into boxes and see that you can't obtain a system with less energy than this.
Author:  sereja 
Tester:  alex_2oo8 
Editorial  http://discuss.codechef.com/problems/SEASTONE 
Tags  dynamicprogramming, medium, oct16, sereja 
Date Added:  10092014 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 