← 返回题目列表

Codeforces · 1958/H

H. 复合法术

中文机器翻译题面 查看原题

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