2907: 小Y的炮
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：
题目描述
小Y最近开发出了批量制造大威力轰山炮的方法。才过去不到几个月，小Y就制造出了M门款式不同的轰山炮。第i门轰山炮发射一次，能使一座当前高度不高于Ai的山的高度降低Di（当然山的高度不能轰到0以下）。应政府要求，小Y要用他开发的轰山炮轰平开发区的几座山。由于开发区急需土地资源，政府要求小Y轰平尽量多的山（轰平：使山的高度降低至0）。 但是小Y制造的弹药有限，导致他最多只能发射K次。 小Y想知道，他最多能轰平几座山？轰平这些山后，弹药最多还够他发射几次？
输入
第一行三个正整数N,M,K，分别表示山的数目、轰山炮的款式数目、最多发射次数。 接下来N行，每行一个正整数Hi，表示第i座山的高度，输入数据保证Hi是降序的（从大到小）。 接下来M行，每行两个正整数Ai,Di，分别表示第i款轰山炮能轰的山的最高高度，和轰掉的山高度的减少值。
输出
一行两个整数Max,Remain,分别表示最多轰平的山的数目和轰平这些山后最多的剩余发射次数。
样例输入 复制
3 2 3
8
6
2
10 6
6 5样例输出 复制
2 1提示
【样例解释】 将高度为6和高度为2的山轰平，使用第一款轰山炮，各只需1次即可轰平。高度为8的山最少需要2次，弹药不够用。所以最多轰平2座山，剩余1次发射次数。
【数据范围】 20%的数据满足N<=100,M<=100,Hi,Ai<=100。 50%的数据满足N<=1000,M<=500。 80%的数据满足N<=250000,M<=500。 20%、50%、80%的数据均满足Hi,Ai<=1000000。 100%的数据满足N<=250000,M<=500,K,Hi,Ai<=10^18,Di<=500。