#P6319. 「JOI 2014 Final」IOI 馒头

    ID: 5808 传统题 1000ms 256MiB 尝试: 2 已通过: 1 难度: 4 上传者: 标签>难度分类普及+/提高-贪心排序贪心排序与序列处理一维前缀和动态规划0/1 背包倒序更新避免重复使用CF1600

「JOI 2014 Final」IOI 馒头

「JOI 2014 Final」IOI 馒头

题目描述

译自 JOI 2014 Final T2「IOI 饅頭」

有 MM 种互不相同的馒头各一个,第 ii 个馒头卖 PiP_i 元。

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

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

每个馒头至多出售一次,每种包装盒最多购买一个。盒子不必装满,未售出的馒头不产生收入或损失;可以不购买任何盒子、不出售任何馒头,此时利润为 00。

输入格式

第一行两个正整数 M,NM,N,意义如题目描述;
接下来 MM 行,每行一个正整数 PiP_i,表示第 ii 个馒头的价格;
接下来 NN 行,每行两个正整数 Cj,EjC_j,E_j,表示第 jj 个包装盒最多能装 CjC_j 个馒头,花费 EjE_j 元。

输出格式

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

样例输入 1

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

样例输出 1

480

样例输入 2

2 2
1000
2000
1 6666
1 7777

样例输出 2

0

样例输入 3

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

样例输出 3

450

样例 1 说明

购买第 1,21,2 个盒子,成本 100+120=220100+120=220。把四个馒头分别装入这两个盒子并全部售出,收入 180+160+170+190=700180+160+170+190=700,利润 700−220=480700-220=480。

数据范围与提示

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

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

Subtask 追加限制 分值
11 N≤10N\le 10 2525
22 Cj≤10C_j\le 10 3535
33 无追加限制 4040