问题2792--打怪兽(monster)

2792: 打怪兽(monster)

时间限制: 1 Sec  内存限制: 128 MB
提交: 44  解决: 14
[提交] [状态] [讨论版] [命题人:]

题目描述

BSNY在玩打怪兽游戏。他需要操作m个英雄依次打败n只怪兽,每个英雄的力量值为pi, 一天时间最多可以打si只怪物;每只怪物的力量值为ai。
当新的一天开始时,BSNY可以选择其中一个英雄去打怪。这个英雄按顺序依次去打未打死的怪兽,只要英雄的力量pi>=怪物力量ai,就可以打死怪兽,这一天最多打死si只。但一旦英雄力量pi<怪物力量ai,当天战斗即结束,该怪兽未死,需要第二天换英雄来打。
BSNY想知道,如何安排每一天的英雄(英雄可以多次出战),可以最少天数打败所有怪兽,输出最少天数。如果无法打败所有怪兽,输出”-1”。

输入

包含多组测试数据,第一行输入T,表示有T组测试数据
每组测试数据第一行输入n,然后第二行输入n个整数ai,表示按顺序依次要打的怪兽的力量值。第三行输入m,然后m行,每行输入pi和si,表示每个英雄的力量值和一天内最多打怪兽的数量。

输出

输出最少天数。如果无法打败所有怪兽,输出”-1”。

样例输入 Copy

2
6
2 3 11 14 1 8
2
3 2
100 1
5
3 5 100 2 3
2
30 5
90 1

样例输出 Copy

5
-1

提示

第一组数据,第一天第1个英雄可以打败2只怪兽,后面每一天都由第2个英雄打1个怪兽,总共需要5天。
第二组数据,力量值为100的怪兽没有影响可以打败。
【数据规模和约定】
40%数据  1<=n, m<=2000
100%数据 1<=n, m<=200000, 1<=ai, pi,<=10^9, 1<=si<=n,  1<=T<=100

来源/分类