您玩电脑游戏。在这个游戏中,你带领一支由 $$$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$$$)。
示例
输入 #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
输出 #1
5 -1