问题2683--佐仓绫音的号哭

2683: 佐仓绫音的号哭

时间限制: 1 Sec  内存限制: 128 MB
提交: 64  解决: 23
[状态] [讨论版] [提交] [命题人:]
题目描述

   兰被献祭给了巴巴恩波神,为了救回兰,CiRCLE的众人决定组成小队击败巴巴恩波神,但巴巴恩波神拥有许多分身,需要将分身悉数消灭才能击败巴巴恩波神。

   巴巴恩波神共有n个分身,每个分身都有一个能力值a,小队有m名成员,每个成员有一个力量p和耐力s,当该成员的力量s大于等于该分身的能力值a时,该分身可被该成员击败。成员耐力值s代表该成员每天可进行s场战斗,小队每天可任意派出一名成员与分身战斗,必须按照从左到右的顺序与分身战斗,当该成员当天连续进行s场战斗或该成员力量p小于当前分身能力值a时,成员归队,当天结束。问最少多少天可击败所有分身。

输入

   多实例,首先输入一个正整数t (1<=t<=100000),表示共有t组实例,对于每组实例,第一行输入一个正整数n (1<=n<=200000),表示巴巴恩波神分身数量,第二行输入n个正整数,表示每个分身的能力值a (1<=a<=1000000000),第三行输入一个正整数m (1<=m<=200000),表示小队成员数量,接下来m行每行两个正整数p (1<=p<=1000000000)s (1<=s<=n),分别表示成员的力量值和耐力值。

    保证所有实例的n+m之和不大于200000

输出

   对于每组实例,输出一行,为击败所有分身的最少天数,若无法击败所有分身,输出-1

样例输入 Copy
6
2 3 11 14 1 8
2
3 2
100 1
样例输出 Copy
5
来源/分类