Migrated from Lutece 378 Haberdasher

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

There is a haberdasher named ALIBABA, who is also a predictor, has predicted the price of some goods for a few days. Every day he can buy some goods or/and sell some goods to earn money. However, he only has a small room to store goods, so he can’t buy too many goods even if they are profitable. Now he is wondering the maximum money he can earn in these days. Note that every kind of goods has an infinite supply, and ALIBABA has enough money to buy them.

Input

The first line of the input is an integer $T$ ($T\leq 50$), which stands for the number of test cases you need to solve.

Every test case begins with three integers $N$($N\leq 100$), $M$($M\leq 20$), $V$($V\leq 1000$), where $N$ is the number of days, $M$ is the number of goods, and $V$ is the maximum volume of his small room to store goods. Then $M$ integers on the next line specify the volume from goods $1$ to goods $M$. Finally $N$ lines with $M$ integers follow, where the $j_{th}$ integer on the $i_{th}$ line specifies the $j_{th}$ goods’ price in the $i_{th}$ day.

All numbers not specified are positive and not greater than $1000$.

Output

For every test case, you should output Case #k: on a single line first, where $k$ indicates the case number and starts at $1$. Then output the maximum money ALIBABA can earn in these days.

Samples

2
2 1 13
3 
2 
4
3 2 7
3 1 
5 2 
6 5 
7 3

Case #1: 8
Case #2: 23

Resources

The 9th UESTC Programming Contest Final