" 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 weaponaries. 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 weaponaries .

"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: no of batches , m:  no of weaponaries per batch , k : Money wayne can spend on weaponaries 

n intergers giving cost of opening the ith batch
n*m numbers denoting cost of jth object from ith batch
n*m numbers denoting the rating oj jth object from ith batch

Output

The maximum power rating Wayne could afford 

Constraints :
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