终于，小 Q 在 RPG 游戏中达到了 $10^5$ 级并获得了他的武器，现在他试图尽快击败 Boss。Boss 拥有 $H$ 点生命值（HP），小 Q 需要造成至少 $H$ 点伤害才能击败 Boss。

小 Q 学习了 $n$ 个技能，编号为 $1, 2, \dots, n$。每个技能不能重复使用，因为小 Q 没有足够的时间等待技能冷却。假设小 Q 在第 $x$ 帧使用第 $i$ 个技能，他所控制的角色需要 $t_i$ 帧来完成动作，这意味着小 Q 在第 $(x + t_i)$ 帧之前不能使用其他技能。第 $i$ 个技能的伤害序列长度为 $len_i$，这意味着如果小 Q 在第 $x$ 帧使用第 $i$ 个技能，该技能将在第 $(x + j)$ 帧造成 $d_{i,j}$ ($0 \le j < len_i$) 点伤害。注意 $len_i$ 可以大于 $t_i$，例如，燃烧技能可以长时间灼烧 Boss，但施放火焰只需要很短的时间。

游戏从第 $0$ 帧开始。你的任务是帮助小 Q 尽快击败 Boss，或者判断小 Q 是否无法在每个技能最多使用一次的情况下击败 Boss。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 100$)，表示测试用例的数量。对于每个测试用例：

第一行包含两个整数 $n$ 和 $H$ ($1 \le n \le 18, 1 \le H \le 10^{18}$)，分别表示技能数量和 Boss 的生命值。

对于每个技能，第一行包含两个整数 $t_i$ 和 $len_i$ ($1 \le t_i, len_i \le 100\,000$)，第二行包含 $len_i$ 个整数 $d_{i,0}, d_{i,1}, \dots, d_{i,len_i-1}$ ($1 \le d_{i,j} \le 10^9$)。

保证所有 $len_i$ 的总和不超过 $3\,000\,000$，且满足 $n > 10$ 的测试用例不超过 $5$ 个。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示击败 Boss 的最早帧数。如果无法击败 Boss，请输出“-1”。

样例

样例输入 1

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

1
2
-1