Qualification Round (Large)

The qualification round of a programming contest just ended. You advanced, and you want to know how many of your fellow contestants advanced with you. The only information you have is how many people solved each problem.

The qualification round consisted of $P$ problems, and problem $i$ (for $0 \le i \le P-1$) was fully solved by $S_i$ contestants. A contestant had to solve $C$ problems to advance to the next round. Solving the same problem twice counts once, so every contestant who advanced solved at least $C$ distinct problems.

Using only that information, find the maximum number of contestants who could have advanced.

The first line of the input gives the number of test cases, $T$. $T$ lines follow. Each consists only of space separated integers: first $P$, then $C$, then the $P$ integers $S_0$ through $S_{P-1}$.

Limits

• $1 \le T \le 100$
• $1 \le C \le P \le 60$
• $0 \le S_i \le 10^{17}$

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is the maximum number of contestants who could have advanced, that is, the maximum number of contestants who could have solved at least $C$ distinct problems.

$y$ can be as large as $6 \times 10^{18}$, so use a 64 bit integer type.