Problem Description

Dr. Patel has $N$ stacks of plates. Each stack contains $K$ plates. Each plate has a positive beauty value, describing how beautiful it looks.

Dr. Patel would like to take exactly $P$ plates to use for dinner tonight. If he would like to take a plate in a stack, he must also take all of the plates above it in that stack as well.

Help Dr. Patel pick the $P$ plates that would maximize the total sum of beauty values.

Input Format

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each test case begins with a line containing the three integers $N$, $K$ and $P$. Then, $N$ lines follow. The $i$-th line contains $K$ integers, describing the beauty values of each stack of plates from top to bottom.

Output Format

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 total sum of beauty values that Dr. Patel could pick.

2
2 4 5
10 10 100 30
80 50 10 50
3 2 3
80 80
15 50
20 10

Case #1: 250
Case #2: 180

Hint

In Sample Case #1, Dr. Patel needs to pick $P=5$ plates:

• He can pick the top $3$ plates from the first stack ($10+10+100 = 120$).
• He can pick the top $2$ plates from the second stack ($80+50=130$) .

In total, the sum of beauty values is $250$.

In Sample Case #2, Dr. Patel needs to pick $P=3$ plates:

• He can pick the top $2$ plates from the first stack ($80+80=160$).
• He can pick no plates from the second stack.
• He can pick the top plate from the third stack ($20$).

In total, the sum of beauty values is $180$.

Limits

$1 \le T \le 100$.

$1 \le K \le 30$.

$1 \le P \le N \times K$.

The beauty values are between $1$ and $100$, inclusive.

Test Set 1

$1 \le N \le 3$.

Test Set 2

$1 \le N \le 50$.