With the end of the War of the Ring, the order is restored and Aragorn started to relocate the war refugees to their respective homes. A new problem arose as some of the old places were destroyed and thus became unlivable.
You are hired to help with the relocations of the refugees. Assume that there are n livable counties in Middle Earth and each county can support a different population size. Aragorn came up with a proposal for the counties such that the number of refugees is equal to the total capacity limits of the counties (otherwise where'd they go?).
All the refugees are living in the refugee camp at the moment. Your end goal is to send them to n different counties. Thus, your first target is to partition the population into n groups such that each group can be sent to the corresponding county.
Grouping the refugees is not easy, because most people would want their families, relatives, and friends to be in the same county. So, you decided to do the grouping in multiple steps. Assume that initially, there is a single group of people. In each step, you can take any group of refugees with a total population of p and divide them into at most k groups with an arbitrary number of people in each of the k groups. As you have to talk to all the people you are grouping, the cost of doing this operation is p. At any step, the refugees are not allowed to regroup again.
So, you want to group the refugees following the above strategy with minimized cost.
Input
Input starts with an integer T (≤ 15), denoting the number of test cases.
Each case starts with a line containing two integers n (2 ≤ n ≤ 105) and k (2 ≤ k ≤ n). Next line contains n space separated integers between 1 and 106 denoting the capacities of the counties. The total population is equal to the summation of all the capacities given.
Output
For each case, print the case number and the minimum possible cost.
Sample
| Sample Input | Sample Output |
|---|---|
4 4 2 7 1 4 5 3 3 8 9 10 9 4 1 1 1 1 1 1 1 1 1 4 3 1 2 14 30 | Case 1: 32 Case 2: 27 Case 3: 16 Case 4: 50 |
Notes
- For case 1, there are 17 refugees.
- In step 1, we partition them into two groups (it's allowed, since k is 2) with groups of population 10 and 7 and the cost of this step is 17.
- In step 2, we partition the group with 10 refugees into two groups having sizes 5 and 5 respectively. The cost of this operation is 10.
- Then finally in step 3, we partition of the group of 5 people into two groups having 1 and 4 refugees. The cost of this operation is 5. So, the overall cost is 17 + 10 + 5 = 32.
- Dataset is huge, use faster I/O methods.