Monocarp 玩的是一款奇幻角色扮演游戏。他的角色是法师,所以他会施展法术。他知道的法术有两种——基本法术和复合法术。
Monocarp的法术书中共有$$$n$$$个基本法术,编号从$$$1$$$到$$$n$$$。每个基本法术只会改变目标的生命值:要么减少,要么增加。第 $$$i$$$ 个基本法术会将目标的生命值改变 $$$b_i$$$(如果 $$$b_i$$$ 为非负数则增加 $$$b_i$$$,如果 $$$b_i$$$ 为负数则减少 $$$|b_i|$$$)。如果目标的生命值降至 $$$0$$$ 或更低,它就会死亡,并且接下来对其施展的所有法术都不起作用。
法术书中还有$$$m$$$复合法术,编号从$$$n+1$$$到$$$n+m$$$。每个复合法术都是一系列其他法术,按特定顺序施展。复合法术可以由基本法术和复合法术组成;第 $$$i$$$ 个咒语由 $$$s_i$$$ 其他咒语组成,并且每个咒语的索引都严格小于 $$$i$$$(因此不存在复合咒语无限施放彼此的情况)。因此,实际上,每个复合法术都可以被视为基本法术的有限序列,尽管其长度可能很大。请注意,同一法术可以在复合法术中多次出现。
Monocarp 决定施放他法术书中的第 $$$(n+m)$$$ 法术。该法术的目标是一个初始生命值为$$$hp$$$的怪物。 Monocarp想知道怪物是否会被杀死,如果会被杀死,哪个基本法术会杀死它。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。
每个测试用例给出如下:
- 第一行包含两个整数 $$$n$$$ 和 $$$hp$$$ ($$$1 \le n \le 5000$$$; $$$1 \le hp \le 10^{9}$$$) — 怪物的基本法术数量和初始生命值;
- 第二行包含 $$$n$$$ 整数 $$$b_1, b_2, \dots, b_n$$$ ($$$-10^9 \le b_i \le 10^9$$$) — 基本咒语的描述;
- 第三行包含一个整数 $$$m$$$ ($$$1 \le m \le 5000$$$) — 复合咒语的数量;
- 然后是 $$$m$$$ 行,这些行中的第 $$$i$$$ 描述了第 $$$(n+i)$$$ 个咒语:它以整数 $$$s_{n+i}$$$ ($$$1 \le s_{n+i} \le 5000$$$) 表示咒语的长度(它包含的咒语数量);然后是从 $$$1$$$ 到 $$$(n+i-1)$$$ 的整数序列,表示咒语的序列。
输入的附加限制:
- 所有测试用例的 $$$n$$$ 总和不超过 $$$5000$$$;
- 所有测试用例的 $$$m$$$ 总和不超过 $$$5000$$$;
- 所有测试用例的所有复合咒语的总长度不超过 $$$5000$$$。
输出
对于每个测试用例,打印一个整数:
- 如果怪物死亡,则打印杀死怪物的基本法术的索引;
- 否则,打印 $$$-1$$$。
示例
输入 #1
4 4 9 1 -2 3 -4 3 3 1 4 3 4 1 2 1 2 6 6 5 6 5 6 5 4 9 1 -2 3 -4 3 3 1 4 3 4 1 2 1 2 7 6 5 6 5 6 6 5 3 31 -10 -20 30 1 6 1 2 3 1 2 3 6 20 -1 -5 -9 -7 -1 -1 4 3 6 5 2 4 3 3 7 6 6 4 8 4 4 6 7 3 6 5 7
输出 #1
4 4 -1 -1