Time Limit: 3000 MS    Memory Limit: 65536 K 


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.


The first line of the input is an integer T (T<=50), which stands for the number of test cases you need to solve. Every test case begins with three integers N(N<=100), M(M<=20), V(V<=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 jth integer on the ith line specifies the jth goodsĄ¯ price in the ith day. All numbers not specified are positive and not greater than 1000.


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.

Sample Input

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

Sample Output

Case #1: 8 Case #2: 23


The 9th UESTC Programming Contest Final