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

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

hide comments
2020-08-20 16:12:28
0/1-Knapsack..1 go
2020-04-30 08:25:43
cool knapsack
2020-04-09 11:12:51
0/1 knapsack.
And didn't even apply DP,just plain recursion.
2018-12-18 08:38:47
@heshamovic can u share more /explain
2018-09-15 00:04:25
0-1 knapsack easy one!!!!!!!
2018-09-06 21:49:04
can be solved by binary search
2016-06-28 15:30:15
simple knapsack 0-1
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.