Avengers are getting ready for the war. All of them lost a lot of money in the previous battle. But since Iron Man was quite rich he was going to buy some new weapons for avengers. He is not that much rich and has only little amount of money in his bank account.

He visits the weapon store and finds that weapons are stored in different rooms. Each room have unbounded number of weapons. To buy these weapons Iron Man initially need to pay the prize to for opening the room. Jarvis being quite smart collected all the information for the Iron Man to help him get the weapons with maximum power in the given amount of money. Jarvis gets the information as :
1) Cost needed to open a room
2) Number of weapons in the given room with their cost and power

Since Jarvis is busy on schedule for planning the strategies about the war. You are required to help the Iron Man to find the maximum power he can achieve for his fellow with his bank balance. He may spend all the money he have in his bank.

INPUT FORMAT:

First line contains a single integer t denoting the number of test cases then for each test case three space seperated integers n , m, k are given in a line where n - number of rooms m - number of weapons in each room k - Bank Balance of Iron Man

next line contains n space separated integers denoting the cost of opening the room

Then next n lines contains m space separated integers denoting cost Again the next n line contains m space separated integers denoting the power.
In Brief :

t 
n m k 
n space seperated integers 
n * m integers - for cost 
n * m integers - for power

See sample if still have doubt on input format

OUTPUT:

Output the maximum power IronMan could afford

Constraints :

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

Problem Source : SPOJ