H. Составные заклинания
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Монокарп играет в фэнтезийную РПГ. Его персонаж — маг, поэтому он колдует заклинания. Существует два типа заклинаний, которые он знает — базовые заклинания и составные заклинания.

В книге заклинаний Монокарпа есть $$$n$$$ базовых заклинаний, пронумерованных от $$$1$$$ до $$$n$$$. Каждое базовое заклинание просто изменяет здоровье цели: либо уменьшает его, либо увеличивает. $$$i$$$-е базовое заклинание изменяет значение здоровья цели на $$$b_i$$$ (увеличивает на $$$b_i$$$, если $$$b_i$$$ неотрицательное, или уменьшает на $$$|b_i|$$$, если $$$b_i$$$ отрицательное). Если значение здоровья цели становится равным $$$0$$$ или ниже, она умирает, и все следующие заклинания, нацеленные на нее, ничего не делают.

Также в книге заклинаний есть $$$m$$$ составных заклинаний, пронумерованных от $$$n+1$$$ до $$$n+m$$$. Каждое составное заклинание — это последовательность других заклинаний, колдуемых в определенном порядке. Составное заклинание может состоять как из базовых заклинаний, так и из составных заклинаний; $$$i$$$-е заклинание состоит из $$$s_i$$$ других заклинаний, и каждое из этих заклинаний имеет индекс строго меньший $$$i$$$ (таким образом, не возникает ситуации, когда составные заклинания бесконечно колдуют друг друга). Таким образом, каждое составное заклинание можно рассматривать как конечную последовательность базовых заклинаний, хотя его длина может быть огромной. Обратите внимание, что одно и то же заклинание может появляться в сложном заклинании несколько раз.

Монокарп решил колдовать $$$(n+m)$$$-е заклинание из своей книги заклинаний. Цель этого заклинания — монстр с начальным значением здоровья $$$hp$$$. Монокарп хочет знать, умрет ли монстр или нет, и если он умрет, какое базовое заклинание его убьет.

Входные данные

Первая строка содержит одно целое число $$$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$$$.
Пример
Входные данные
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