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

hide comments
Rishabh: 2015-02-16 08:26:33

Awesome!

Last edit: 2015-02-16 09:27:13
|RAMSDEN|: 2014-12-15 21:36:29

Awesome :)

Yusro Tsaqova: 2013-08-14 03:49:47

@Roman Thoppilan
Example :
1
2 2 7
2 2
2 1
1 2
10 2
3 10
the answer must be 23, right ?
My code answer 22, and still got acc

Romal Thoppilan: 2013-02-25 12:03:55

@mario : once the seal is opened , you can take "unbounded" amount of weapons from it. Wayne opens the second seal only and takes 8 (2=>5) weapons , making it 8*5 = 40

MarioYC: 2013-02-21 18:11:40

Why is the answer to the example 40?

3 2 3 2
4 5 6 5

The sum of all shuold be 30 at most. Right?

:D: 2013-02-16 23:02:33

Thanks. Problem made visible again.

It's still not in the description, so am I to assume cost is always a positive integer?

Last edit: 2013-02-16 23:05:11
:D: 2013-02-16 20:17:09

Multiple times. It says the number is unbounded.

Ruben Andrist: 2013-02-16 20:17:09

are the weapons unique or can they be bought multiple times?

:D: 2013-02-16 20:17:09

Please check your test cases. Also give exact bounds (lower and upper bounds) cost and rating values. Is 0 cost possible? What to print if maximum rating is unbounded?

Last edit: 2013-02-09 13:12:35

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