1078: IOI 馒头

内存限制:128 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:4 通过:2

题目描述

https://loj.ac/p/2757


有  M种互不相同的馒头各一个,第 i 个馒头卖 Pi 元。

有 N 个包装盒,第 j 个包装盒最多能装 Cj 个馒头,买第 j 个包装盒的花费为 Ej 元。要求只能将一些馒头放进包装盒中打包出售,不能零售,当然也可以不出售某些馒头(卖剩的馒头被出题人吃了,出题人还吃得津津有味~)。售出一盒馒头得到的利润为盒内所有馒头的价格减去包装盒的价格。

现在买下(这  N 个包装盒)其中的一些包装盒(也可以不买,还可以全买),将馒头打包出售,求最大可能利润。

输入格式

第一行两个正整数M , N ,意义如题目描述;
接下来M  行,每行一个正整数 Pi ,表示第 i 个馒头的价格;
接下来 N 行,每行两个正整数 Cj,Ej表示第 j 个包装盒最多能装 Cj 个馒头,花费 Ej 元。

输出格式

一行一个整数,表示最大可能利润。


输入格式


输出格式

For each game, print a line consisting of the input, followed by a space, followed by A or B to
indicate the eventual winner of the game.

输入样例 复制

4 3
180
160
170
190
2 100
3 120
4 250

输出样例 复制

480

数据范围与提示

10 4
200
250
300
300
350
400
500
300
250
200
3 1400
2 500
2 600

	1 900



输出


450


分类标签