1078: IOI 馒头
内存限制：128 MB
时间限制：1 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：14
通过：2
题目描述
有 M种互不相同的馒头各一个，第 i 个馒头卖 Pi 元。
有 N 个包装盒，第 j 个包装盒最多能装 Cj 个馒头，买第 j 个包装盒的花费为 Ej 元。要求只能将一些馒头放进包装盒中打包出售，不能零售，当然也可以不出售某些馒头（卖剩的馒头被出题人吃了，出题人还吃得津津有味~）。售出一盒馒头得到的利润为盒内所有馒头的价格减去包装盒的价格。
现在买下（这 N 个包装盒）其中的一些包装盒（也可以不买，还可以全买），将馒头打包出售，求最大可能利润。
输入格式
第一行两个正整数M , N ，意义如题目描述；
接下来M 行，每行一个正整数 Pi ，表示第 i 个馒头的价格；
接下来 N 行，每行两个正整数 Cj，Ej表示第 j 个包装盒最多能装 Cj 个馒头，花费 Ej 元。
对于全部数据，1<=M<= 10^4,1<= N<= 500,1<= P_i,C_j,E_j<=10^4。
输出格式
一行一个整数，表示最大可能利润。
输入样例 复制
4 3
180
160
170
190
2 100
3 120
4 250输出样例 复制
480数据范围与提示
在本例中，我们选择第一、第二个包装盒，第一个包装盒装第 1,2 个馒头，第二个包装盒装第 3,4 个馒头。第一盒馒头的利润是 180+160-100=240 元，
第二盒馒头的利润是 170+190-120=240 元，因此总利润为 240+240=480 元。
样例2：
2 2 1000 2000 1 6666 1 7777输出 0
在本例中，为了最大化利益，最好不买包装盒（也就是不卖馒头）。
样例3：
10 4 200 250 300 300 350 400 500 300 250 200 3 1400 2 500 2 600 1 900 输出450