#2757. 「JOI 2014 Final」IOI 馒头

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: HeRaNO

题目描述

译自 JOI 2014 Final T2「IOI 饅頭

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

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

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

输入格式

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

输出格式

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

样例

样例输入 1

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

样例输出 1

480

样例说明 1

在本例中,我们选择第一、第二个包装盒,第一个包装盒装第 1,2 个馒头,第二个包装盒装第 3,4 个馒头。第一盒馒头的利润是 180+160-100=240 元,第二盒馒头的利润是 170+190-120=240 元,因此总利润为 240+240=480 元。

样例输入 2

2 2
1000
2000
1 6666
1 7777

样例输出 2

0

样例说明 2

在本例中,为了最大化利益,最好不买包装盒(也就是不卖馒头)。

样例输入 3

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

样例输出 3

450

数据范围与提示

对于全部数据, 1\le M\le 10^4,1\le N\le 500,1\le P_i,C_j,E_j\le 10^4

详细子任务及数据满足条件如下表:

Subtask 追加限制 分值
1 N\le 10 25
2 C_j\le 10 35
3 无追加限制 40