Composite Spells
Contest: Kotlin Heroes: Episode 10
Difficulty rating: 2600
Tags: *special, dp

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.

Input format:
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 format:
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$$$.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Example input:
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

Example output:
4
4
-1
-1

Editorial:
First of all, the total health value might be very large. It may grow exponentially, so we can't use basic integer types to handle the health values. Thankfully, Kotlin has a BigInteger class which allows us to deal with arbitrarily large number addition/subtraction in $$$O(S)$$$, where $$$S$$$ is the size of the greater number. Using induction on the total length of the composite spells, we can show that the length of each number is $$$O(\sum s_i)$$$. So, we need a solution that makes $$$O(n + m + \sum s_i)$$$ operations with big integers.
Suppose we calculate the total change of health for every composite spell with dynamic programming (let it be $$$delta_i$$$ for the $$$i$$$-th spell). If we try iterating on components of the spell we cast, we will know our health value after using each component. However, we might miss the moment when the health of the monster went to $$$0$$$ or lower in the middle of a component.
We need a way to know if a spell puts the monster into non-positive health in the middle of casting. Let's consider the minimum value the monster's health becomes during casting the spell. Obviously, if it is positive, then the monster survives the spell, otherwise it dies.
To quickly calculate the minimum health value, let's introduce another dynamic programming: let $$$minDelta_i$$$ be the minimum change of health while the $$$i$$$-th spell is cast. Using the values of $$$delta_i$$$, we can calculate it recursively as follows: let the $$$i$$$-th spell consist of components $$$c_1, c_2, \dots, c_k$$$. The minimum health is achieved when we have finished casting the first several parts of the spell and are in the middle of casting the next part. So, the value of $$$minDelta_i$$$ can be calculated as $$$\min \limits_{j=1}^{k} \sum \limits_{v=1}^{j-1} delta_{c_v} + minDelta_{c_j}$$$, and we can compute it in $$$O(k)$$$ additions/subtractions/comparisons of big integers.
Okay, now we know the value of $$$delta_i$$$ and $$$minDelta_i$$$ for each spell. For each composite spell we cast, we are now able to understand whether it will put the monster's health to $$$0$$$ or lower in the middle of casting. So, to find the basic spell that kills the monster, we can use recursion.
Let $$$rec(remHP, idCompSpell)$$$ be a recursive function that computes the answer if the current health of the monster is $$$remHP$$$, and we cast the spell $$$idCompSpell$$$. We can iterate on the first component of the spell that will bring the monster to non-positive health, and make a recursive call with the health value of the monster right before this component is cast, and the id of this component. Each call decreases the value of $$$idCompSpell$$$ at least by $$$1$$$, so we will call this function at most once for each composite spell, so all calls will work in $$$O(\sum s_i)$$$.
So, the complexity of our solution is $$$O(\sum s_i \cdot (n + m + \sum s_i))$$$.