Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 2536
Best Balance

Time Limit: 2 Seconds      Memory Limit: 65536 KB

FatMouse has just got a baby! In order to control the baby's mouse weight, he bought a balance as well as some weights. By placing his baby on one side of the balance and some of the weights on the other, he could read how heavy his baby is. However, the baby is catching on weight so fast that FatMouse worries he would not be able to do that one day. Thus he has decided to purchase several other weights. He can choose how heavy these weights are. And of course he wants to maximize the smallest weight that this balance can not measure.

All weights are integers (in pounds). The balance can detect and compensate any fractional weight (less than one pound) difference between two sides. FatMouse never places any weight on the same side of his baby.

Input Description

Standard input will contain multiple test cases. The first line of the input is a single integer T (1 <= T <= 50) which is the number of test cases. T test cases follow, each preceded by a single blank line.

Each case starts with two integers n (0 <= n <= 20) and k (0 <= k <= 10), where n is the number of the weights that FatMouse currently has, and k is the number of weights that FatMouse is going to purchase. The next n integers ci (0 <= i < n, 1 <= ci < 100,000) give the weights (in pounds) he currently owns. Two consecutive numbers are separated by a single space.

Output Description

Results should be directed to standard output. Start each case with "Case #:" on a single line, where # is the case number starting from 1. Two consecutive cases should be separated by a single blank line. No blank line should be produced after the last test case.

The output of each test case should be a single integer, which is the maximized smallest weight that he will not be able to measure.

Sample Input

4

3 1 1 2 4

3 2 1 3 5

2 1 1 1

3 0 1 2 5

Sample Output

Case 1:
16

Case 2:
24

Case 3:
6

Case 4:
4


Source: Asia 2005, Hangzhou (Mainland China), Preliminary
Submit    Status