Mix and Merge

reborn Criterion 2022 Round 18
Limits 1s, 512 MB

You are given an array AA of nn elements and a constant kk. You can perform the following operation on the array —

  • Choose any sub-array of pp elements where 2pk2 \le p \le k and merge the elements into a new element. The pp elements are removed and their sum is inserted as a new element in that place. The cost of this operation is the sum itself.

Calculate the minimum cost to reduce the array to only one element, by performing the mentioned operation as many times needed.

Input

First line of input will contain an integer TT denoting the number of test cases.

For each test case, the first line contains two integers nn and kk, and the second line contains nn integers A1, A2,AnA_1, ~A_2, \dots A_n.

Constraints:

  • 1T1001 \le T \le 100.

  • 1n1001 \le n \le 100.

  • 2k502 \le k \le 50.

  • 1Ai1001 \le A_i \le 100.

Output

For each test case, output a line in the format “Case i: x” without the quotes, where xx is the minimum cost to reduce the array to only one element, by performing the mentioned operation as many times needed.

Sample

InputOutput
1
4 3
1 2 3 4
Case 1: 13

Submit

Login to submit.

Statistics

13% Solution Ratio
MrBrionixEarliest, 1w ago
MrBrionixFastest, 0.3s
MrBrionixLightest, 1.6 MB
MrBrionixShortest, 1025B
Toph uses cookies. By continuing you agree to our Cookie Policy.