C. Greed
time limit per test
8 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Before the battle against the final boss, you are going to buy some items to improve your chances. But this store is a bit different from the ones you are used to: there are $$$N$$$ stacks, the $$$i$$$-th stack contains $$$m_i$$$ items, and the $$$j$$$-th item of the $$$i$$$-th stack adds $$$a_{ij}$$$ attack units to your character. Initially, you can only buy the first item from each stack. When you buy an item, the next one in the stack is unlocked, and you can buy it as well. Additionally, all items have the same price: 15 coins. Your goal is to spend the $$$C$$$ coins you have in order to maximize your attack.

Input

The input will consist of an integer $$$t$$$, followed by $$$t$$$ test cases. In the first line of each case, there will be $$$N$$$ and $$$C$$$. Next, there will be $$$N$$$ lines, the $$$i$$$-th of which describes stack $$$i$$$: first comes $$$m_i$$$, the number of items in that stack, followed by $$$m_i$$$ integers, the $$$j$$$-th of which is $$$a_{ij}$$$.

Output

One line per case with the maximum amount of attack that can be obtained by buying some items in the store.

Scoring

For all test cases, it holds that $$$-10^9 \leq a_{ij} \leq 10^9$$$.

25 points: $$$1 \leq N \leq 12$$$, $$$1 \leq C \leq 150$$$, $$$1 \leq m_i \leq 12$$$, $$$t = 50$$$.

25 points: $$$1 \leq N \leq 60$$$, $$$1 \leq C \leq 1000$$$, $$$1 \leq m_i \leq 60$$$, $$$t = 100$$$.

50 points: $$$1 \leq N \leq 250$$$, $$$1 \leq C \leq 3000$$$, $$$1 \leq m_i \leq 200$$$, $$$t = 150$$$.

Example
Input
3
1 29
4 1 2 3 4
2 30
2 -2 1
3 -1 -1 3
5 90
3 5 1 10
3 6 1 2
3 7 1 3
3 8 1 4
3 9 1 5
Output
1
0
40