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 : 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 5Output:40
hide comments
hkyiitd:
20190308 17:44:42
Getting TLE with O(n*k*k) algo. 

jwalinarora:
20181006 14:26:48
Can it be solved using 2d DP? 

learnerinblack:
20180818 07:48:16
What is answer for this test case?


luka_dzimba911:
20180409 18:44:23
A couple of notes worth reading :


akababa:
20171005 23:16:39
How is the example possible? the sum of all the ratings is less than the answer? 

karikjoshi21:
20170822 12:51:22
AC IN ONE GO ! PRETTY EASY PROBLEM ! 

Sigma Kappa:
20170530 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:
20170523 18:50:20
Thanks @vengatesh15 for the advice :) 

shahzada:
20170308 21:38:57
Done with top down and bottom up both. Easy One :D 

vengatesh15:
20170210 17:38:56
Try to correct the question u haven't specified we can take a weapon multiple times

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