FOODIE - FOODIE
Monica loves cooking and Joey is a big foodie. Monica cooks for him but she cooks way too much and fills the entire refrigerator with dishes.
Joey wants to have all the dishes, but his stomach can accommodate a maximum of k units of food. If he starts having a dish of a particular rack, he has to finish all the dishes of the chosen rack (Monica's rules and regulations :P ).
Now you being a Joey fan, are pretty sure he won't be able to make a good choice of racks and come to his rescue! Find the maximum units of food Joey can consume.
Input
There are t test cases (1 <= t <= 10). In each test case the first line specifies n and k, where n is the number of racks and k is as described in the problem statement (1 <= n <= 100, 1 <= k <= 1000).
Next n lines, first specifies r, the number of dishes in that rack (0 <= r <= 10) followed by r integers denoting the number of food units that particular dish comprises of. Each dish contains a maximum of 1000 food units.
Output
The maximum number of food units Joey can consume.
Example
Input: 2 3 7 3 1 2 3 1 1 2 2 2 3 10 3 4 2 2 2 4 2 3 1 1 1 Output: 7 9
hide comments
akhilesh_2109:
2020-08-20 16:12:28
0/1-Knapsack..1 go
|
|
manish_thakur:
2020-04-30 08:25:43
cool knapsack |
|
amar_shukla1:
2020-04-09 11:12:51
0/1 knapsack.
|
|
joydip007x:
2018-12-18 08:38:47
@heshamovic can u share more /explain
|
|
a161112225:
2018-09-15 00:04:25
0-1 knapsack easy one!!!!!!! |
|
heshamovic:
2018-09-06 21:49:04
can be solved by binary search |
|
chakkriii:
2016-06-28 15:30:15
simple knapsack 0-1
|
Added by: | stardex |
Date: | 2016-06-10 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 GOSU JS-MONKEY |
Resource: | Own Problem |