BAT1 - BATMAN1

" 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

Added by:Romal Thoppilan
Date:2013-02-06
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own problem

hide comments
2016-10-30 18:47:03
Can cost of a weapon be 0 ???
2016-09-24 12:13:46
@romzee : Any number of batches can be opened ?
2016-06-23 09:54:05
easy one for begginer just use topdown kanpsnap
2016-05-21 06:15:27
@arrow123/
please check with this test case
1
2 2 7
2 2
2 1
1 2
10 2
3 10
2016-05-21 06:14:27
@tsaqova
my code is giving 23 in your test case and i am getting WA
2016-05-20 15:08:29 The Arrow
brilliant dp problem :-)
2016-01-13 19:50:59 Viswanadh
AWW SUM :D
2015-11-01 11:19:01
Nice variation of Knapsack problem.
2015-09-03 10:46:15 Sagnik Mondal
Plz check id 15053835. can figure out why its giving WA
2015-06-11 13:07:14 Agam Gupta
Awesome :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.