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