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

hide comments
hkyiitd: 2019-03-08 17:44:42

Getting TLE with O(n*k*k) algo.

jwalinarora: 2018-10-06 14:26:48

Can it be solved using 2-d DP?

learnerinblack: 2018-08-18 07:48:16

What is answer for this test case?
1
5 10 300
5 6 8 7 1
40 33 39 45 14 4 41 38 7 33
4 46 45 37 1 19 49 5 19 9
12 35 23 30 8 3 50 29 16 28
45 22 46 26 4 46 10 18 29 16
32 16 15 12 25 16 35 47 7 21
24 25 47 41 2 15 40 17 20 42
49 23 24 11 6 3 37 25 10 36
2 26 3 22 40 37 50 37 47 19
6 48 10 9 42 23 14 50 39 26
27 7 3 42 37 19 41 41 9 35

My code is giving 3606 and that on Spojtoolkit is giving 3589. Which one is correct?

luka_dzimba911: 2018-04-09 18:44:23

A couple of notes worth reading :
- you can open any batch and as many you want if you have enough money
- you have unlimited weapons in every batch
- once you open a batch its opened forever
my complexity (n*k^2) if that helps

akababa: 2017-10-05 23:16:39

How is the example possible? the sum of all the ratings is less than the answer?

karikjoshi21: 2017-08-22 12:51:22

AC IN ONE GO ! PRETTY EASY PROBLEM !

Sigma Kappa: 2017-05-30 20:03:11

Not sure if my algo is optimal, but got Accepted after saving time on the DP table initialization. My DP state is at most 2^{21} bits.

Shubham Jadhav: 2017-05-23 18:50:20

Thanks @vengatesh15 for the advice :)

shahzada: 2017-03-08 21:38:57

Done with top down and bottom up both. Easy One :-D

vengatesh15: 2017-02-10 17:38:56

Try to correct the question u haven't specified we can take a weapon multiple times


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