" Lucius Fox: This conversation used to end with an unusual request.
Bruce Wayne: I'm retired.
Lucius Fox: Well let me show you some stuff anyway. Just for old time's sake. "

Eight years after Harvey Dent's death, the Dent Act allowed eradication of organized crime. BATMAN has disappeared. Wayne enterprises is unprofitable after Bruce discontinued his fusion reactor project. A masked man called Bane who was trained under Ra's al Ghul captures Gordon. Bane attacks the Gotham Stock Exchange, using Bruce's fingerprints in a transaction that bankrupts Wayne.

Now that Gotham City was heading into deep deep trouble, Its time for BATMAN to return.

However, since the company no longer belongs to Bruce Wayne, Mr. Wayne has very little funds to spend on buying his weaponries. Mr Fox head him to the place where all weapons are stored.  

Now these weapons come in batches properly sealed for safety. Each of these batches will have an unbounded number of weapons of different types. To buy these weapons Wayne initially need to pay the price for opening the seal. Then each of these weapons have a cost and a power rating associated with it.  Mr Wayne needs to spend wisely on it to maximize the power rating using  limited amount of money.

People of Gotham, he needs your help for choosing his weaponries.

Lucius Fox: It has a long uninteresting name. I just took to calling it... The Bat, and yes, Mr. Wayne, it does come in black.

Input

t, number of testcases
integers n m k, n: number of batches, m: number of weaponries per batch, k : Money Wayne can spend on weaponries
n integers giving cost of opening the ith batch
n*m numbers denoting cost of jth object from ith batch
n*m numbers denoting the rating of jth object from ith batch

Output

The maximum power rating Wayne could afford 

Constraint:

1 <= n, m <= 20
k <= 1000
cost[i] <= 20
rating[i] <= 100

Example

Input:
1
2 4 20
3 4
3 2 3 2
3 2 3 5
3 2 3 2
4 5 6 5

Output:
40