D. Очередная задача на сражение с монстрами
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы играете в компьютерную игру. В этой игре вы являетесь главой партии из $$$m$$$ героев, и вам нужно зачистить подземелье, в котором находится $$$n$$$ монстров. Каждый монстр характеризуется своей силой $$$a_i$$$. Каждый герой характеризуется своей силой $$$p_i$$$ и выносливостью $$$s_i$$$.

Герои чистят подземелье день за днем. В начале каждого дня вы выбираете героя (ровно одного), который пойдет в подземелье в этот день.

Когда герой заходит в подземелье, он начинает сражаться с первым монстром, не побежденным в прошлые дни (т. е. если уже было побеждено $$$k$$$ монстров, то этот герой будет сражаться с монстром под номером $$$k + 1$$$). Когда герой сражается с монстром, возможно два варианта:

  • если сила монстра строго больше силы героя, то герой уходит из подземелья и день заканчивается;
  • иначе монстр считается побежденным.

После победы над монстром герой либо продолжает сражаться с монстрами, либо уходит из подземелья. Он уходит, если он в этот день победил количество монстров, равное его выносливости (таким образом, $$$i$$$-й герой не может победить больше $$$s_i$$$ монстров в течение одного дня), либо если все монстры побеждены — в противном случае герой сражается со следующим монстром. Когда герой покидает пещеру, текущий день заканчивается.

Ваша задача — победить всех монстров. Какое минимальное количество дней вам понадобится для этого? Каждый день вы выбираете ровно одного героя; возможно, некоторые герои не будут сражаться вообще, а некоторые будут сражаться несколько раз.

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

Первая строка содержит целое число $$$t$$$ ($$$1 \le t \le 10^5$$$) — количество наборов входных данных. Каждый набор данных выглядит следующим образом.

Первая строка содержит целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество монстров в подземелье.

Вторая строка содержит $$$n$$$ чисел $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i \le 10^9$$$), где $$$a_i$$$ — сила $$$i$$$-го монстра.

Третья строка содержит целое число $$$m$$$ ($$$1 \le m \le 2 \cdot 10^5$$$) — количество героев в вашей партии.

После следуют $$$m$$$ строк, каждая описывает героя. Каждая такая строка содержит два числа $$$p_i$$$ и $$$s_i$$$ ($$$1 \le p_i \le 10^9$$$, $$$1 \le s_i \le n$$$) — силу и выносливость $$$i$$$-го героя.

Гарантируется, что сумма $$$n + m$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

На каждый набор входных данных выведите одно число — минимальное количество дней, которое вам нужно потратить для победы над всеми монстрами (или $$$-1$$$, если это невозможно).

Пример
Входные данные
2
6
2 3 11 14 1 8
2
3 2
100 1
5
3 5 100 2 3
2
30 5
90 1
Выходные данные
5
-1