当前没有测试数据。

题目描述

After the struggle of graduating from college, TangTang is about to move from a student apartment to his new home. TangTang has n items to move, the i-th of which is of volume $v_i$. He can pack all these items into at most K boxes of the same volume. TangTang is so clever that he uses the following strategies for packing items: - Each time, he would put items into a box by the next strategy, and then he would try to fill another box. - For each box, he would put an unpacked item of the largest suitable volume into the box repeatedly until there is no such item that can be fitted in the box. Now, the question is what is the minimum volume of these boxes required to pack all items.

输入格式

There are multiple test cases. The first line contains an integer T ($1 \leq T \leq 20$), indicating the number of test cases. Test cases are given in the following.For each test case, the first line contains two integers n, K ($1 \leq n, K \leq 1000$), representing the number of items and the number of boxes respectively.The second line contains n integers $v_1$​, $v_2$​, ……, $v_n$​ ($1 \leq v_1, v_2, \ldots, v_n \leq 1000$), where the i-th integer $v_i$​ represents the volume of the i-th item.

输出格式

For each test case, output "Case #x: y" in one line (without quotes), where x indicates the case number starting from 1, and y denotes the answer to this test case.

样例

样例输入 1

1
5 3
1 2 3 4 5

样例输出 1

Case #1: 5