Composite Spells
Description
Monocarp plays a fantasy RPG. His character is a mage, so he casts spells. There are two types of spells he knows — basic spells and composite spells.
There are $n$ basic spells in Monocarp's spell book, numbered from $1$ to $n$. Each basic spell simply changes the health of the target: either decreases it or increases it. The $i$-th basic spell changes the target's health value by $b_i$ (increases by $b_i$ if $b_i$ is non-negative, or decreases by $|b_i|$ if $b_i$ is negative). If the target's health value goes to $0$ or below, it dies, and all next spells cast at it do nothing.
There are also $m$ composite spells in the spell book, numbered from $n+1$ to $n+m$. Each composite spell is a sequence of other spells, cast in specific order. A composite spell can consist both of basic spells and composite spells; the $i$-th spell consists of $s_i$ other spells, and each of those spells has index strictly less than $i$ (so there is no situation that composite spells infinitely cast each other). So, actually, each composite spell can be considered a finite sequence of basic spells, although its length might be huge. Note that the same spell can appear in a composite spell multiple times.
Monocarp has decided to cast the $(n+m)$-th spell from his spell book. The target of this spell is a monster with an initial health value of $hp$. Monocarp wants to know whether the monster will be killed or not, and if it will be killed, which basic spell will kill it.
The first line contains one integer $t$ ($1 \le t \le 1000$) — the number of test cases.
Each test case is given as follows:
- the first line contains two integers $n$ and $hp$ ($1 \le n \le 5000$; $1 \le hp \le 10^{9}$) — the number of basic spells and the initial health value of the monster;
- the second line contains $n$ integers $b_1, b_2, \dots, b_n$ ($-10^9 \le b_i \le 10^9$) — the descriptions of basic spells;
- the third line contains one integer $m$ ($1 \le m \le 5000$) — the number of composite spells;
- then $m$ lines follow, the $i$-th of these lines describes the $(n+i)$-th spell: it begins with an integer $s_{n+i}$ ($1 \le s_{n+i} \le 5000$) denoting the length of the spell (the number of spells it consists of); then a sequence of integers from $1$ to $(n+i-1)$ follows, denoting the sequence of spells.
Additional constraints on the input:
- the sum of $n$ over all test cases does not exceed $5000$;
- the sum of $m$ over all test cases does not exceed $5000$;
- the total length of all composite spells over all test cases does not exceed $5000$.
For each test case, print one integer:
- if the monster dies, print the index of the basic spell that kills the monster;
- otherwise, print $-1$.
Input
The first line contains one integer $t$ ($1 \le t \le 1000$) — the number of test cases.
Each test case is given as follows:
- the first line contains two integers $n$ and $hp$ ($1 \le n \le 5000$; $1 \le hp \le 10^{9}$) — the number of basic spells and the initial health value of the monster;
- the second line contains $n$ integers $b_1, b_2, \dots, b_n$ ($-10^9 \le b_i \le 10^9$) — the descriptions of basic spells;
- the third line contains one integer $m$ ($1 \le m \le 5000$) — the number of composite spells;
- then $m$ lines follow, the $i$-th of these lines describes the $(n+i)$-th spell: it begins with an integer $s_{n+i}$ ($1 \le s_{n+i} \le 5000$) denoting the length of the spell (the number of spells it consists of); then a sequence of integers from $1$ to $(n+i-1)$ follows, denoting the sequence of spells.
Additional constraints on the input:
- the sum of $n$ over all test cases does not exceed $5000$;
- the sum of $m$ over all test cases does not exceed $5000$;
- the total length of all composite spells over all test cases does not exceed $5000$.
Output
For each test case, print one integer:
- if the monster dies, print the index of the basic spell that kills the monster;
- otherwise, print $-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
4
4
-1
-1