Problem Description

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 $i$-th skill at the $x$-th frame, the actor controlled by him will take $t_i$ frames to perform, which means Little Q will not be allowed to use other skills until the $(x+t_i)$-th frame. The length of the damage sequence of the $i$-th skill is $len_i$, which means the skill will cause $d_{i,j}$ ($0\leq j < len_i$) units of damage at the $(x+j)$-th frame if Little Q uses the $i$-th skill at the $x$-th frame. Note that $len_i$ can be greater than $t_i$, 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.

Input

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

The first line contains two integers $n$ and $H$ ($1 \leq n \leq 18$, $1\leq H\leq 10^{18}$), denoting the number of skills and the HP of the boss.

For each skill, the first line contains two integers $t_i$ and $len_i$ ($1 \leq t_i,len_i\leq 100\,000$), the second line contains $len_i$ integers $d_{i,0},d_{i,1},\dots,d_{i,len_i-1}$ ($1\leq d_{i,j}\leq 10^9$).

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

Output

For each test case, output a single line containing an integer, denoting the first frame to beat the boss. If it is impossible to beat the boss, please print ''$\texttt{-1}$'' instead.

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