CF1257D.Yet Another Monster Killing Problem

You play a computer game. In this game, you lead a party of $m$ heroes, and you have to clear a dungeon with $n$ monsters. Each monster is characterized by its power $a_i$. Each hero is characterized by his power $p_i$ and endurance $s_i$.

The heroes clear the dungeon day by day. In the beginning of each day, you choose a hero (exactly one) who is going to enter the dungeon this day.

When the hero enters the dungeon, he is challenged by the first monster which was not defeated during the previous days (so, if the heroes have already defeated $k$ monsters, the hero fights with the monster $k + 1$). When the hero fights the monster, there are two possible outcomes:

• if the monster's power is strictly greater than the hero's power, the hero retreats from the dungeon. The current day ends;
• otherwise, the monster is defeated.

After defeating a monster, the hero either continues fighting with the next monster or leaves the dungeon. He leaves the dungeon either if he has already defeated the number of monsters equal to his endurance during this day (so, the $i$-th hero cannot defeat more than $s_i$ monsters during each day), or if all monsters are defeated — otherwise, he fights with the next monster. When the hero leaves the dungeon, the current day ends.

Your goal is to defeat the last monster. What is the minimum number of days that you need to achieve your goal? Each day you have to use exactly one hero; it is possible that some heroes don't fight the monsters at all. Each hero can be used arbitrary number of times.

你正在玩一款电脑游戏。在这款游戏中，你率领一支由 $m$ 名英雄组成的队伍，需要通关一个有 $n$ 只怪物的地下城。每只怪物以其力量值 $a_i$ 表征；每位英雄以其力量值 $p_i$ 和耐力值 $s_i$ 表征。

英雄们按天依次通关地下城。每天开始时，你需恰好选择一名英雄进入地下城。

当英雄进入地下城时，他将面对上一天结束时尚未被击败的第一只怪物（即：若此前各天共已击败 $k$ 只怪物，则该英雄将与第 $k + 1$ 只怪物交战）。英雄与怪物战斗时，有两种可能结果：

• 若怪物的力量 严格大于 英雄的力量，则英雄从地下城撤退，当日结束；
• 否则，该怪物被击败。

击败一只怪物后，英雄可选择继续挑战下一只怪物，或离开地下城。他在以下任一情形发生时离开地下城：

• 他在当天已击败的怪物数量已达其耐力上限（即：第 $i$ 位英雄在单日内最多击败 $s_i$ 只怪物）；
• 所有怪物均已击败。

否则，他将继续挑战下一只怪物。英雄离开地下城后，当日结束。

你的目标是击败最后一只怪物（即第 $n$ 只怪物）。问：达成此目标所需的最少天数是多少？
注意：每天必须且仅能使用一名英雄；允许某些英雄全程不参战；每位英雄可被重复使用任意多次。

The first line contains one integer $t$ ($1 \le t \le 10^5$) — the number of test cases. Then the test cases follow.

The first line of each test case contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of monsters in the dungeon.

The second line contains $n$ integers $a_1$, $a_2$, ..., $a_n$ ($1 \le a_i \le 10^9$), where $a_i$ is the power of the $i$-th monster.

The third line contains one integer $m$ ($1 \le m \le 2 \cdot 10^5$) — the number of heroes in your party.

Then $m$ lines follow, each describing a hero. Each line contains two integers $p_i$ and $s_i$ ($1 \le p_i \le 10^9$, $1 \le s_i \le n$) — the power and the endurance of the $i$-th hero.

It is guaranteed that the sum of $n + m$ over all test cases does not exceed $2 \cdot 10^5$.

第一行包含一个整数 $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$。

For each test case print one integer — the minimum number of days you have to spend to defeat all of the monsters (or $-1$ if it is impossible).

对于每个测试用例，输出一个整数——击败所有怪物所需的最少天数（如果不可能，则输出 $-1$）。