8499: Boss Rush

Finally, Little Q gets his weapon at level 10^5 in the RPG game, now he is trying to beat the boss as soon as possible. The boss has H  units of health point (HP), Little Q needs to cause at least H units of damage to beat the boss.

Little Q has learnt n skills, labeled by $1,2,\dots ,n$. Each skill can not be used multiple times, because there is not enough time for Little Q to wait for the skill to cool down. Assume Little Q uses the ith skill at the x-th frame, the actor controlled by him will take ti  frames to perform, which means Little Q will not be allowed to use other skills until the (x+ti)-th frame. The length of the damage sequence of the i-th skill is leni, which means the skill will cause di,j (0≤j<leni) units of damage at the $(x+j)$-th frame if Little Q uses the i-th skill at the x-th frame. Note that leni can be greater than ti, for example, the burning skill can burn the boss for a long period, but takes a little time to cast the fire.

The game starts at the $0$-th frame. Your task is to help Little Q beat the boss as soon as possible, or determine Little Q can't beat the boss using all the skills at most once.

The first line contains a single integer T($1\le T\le 100$), the number of test cases. For each test case:

The first line contains two integers n and H ($1\le n\le 18$, 1≤H≤1018), denoting the number of skills and the HP of the boss.

For each skill, the first line contains two integers ti and leni (1≤ti,leni≤100,000), the second line contains leni integers di,0,di,1,…,di,leni−1 (1≤di,j≤109).

It is guaranteed that the sum of all eni is at most 3,000,000， and there are at most $5$ cases such that n>10.

3
1 100
5 3
50 60 70
2 100
2 3
40 40 100
100 2
20 5
1 1000
1 1
999

1
2
-1