← 返回题目列表

AtCoder · joi2014ho2

B. IOI馒头

中文机器翻译题面 查看原题

配点: 100 点

Incredible Okashi Inc. 是一家生产“incredible okashi”的公司。我们这里将其简称为IOI公司。 IOI公司制作了一款特殊的IOI馒头,所以他们决定出售它。 IOI 是 M 不同类型的包子 1 我一一做了。制作 M 馒头的大小都是一样的,但是每一个的口味不同,所以价格也不同。i 番目 (1 \leqq i \leqq M) 处的面包价格为 P_i 这是一个圆圈。

顺便问一下,你听说过 Just Odd Inventions 吗?这家公司的业务就是制造“只是奇怪的发明”。在这里,我们将其缩写为J​​OI。 IOI将向JOI订购高质量的包子包装盒。 JOI生产的馒头盒是 N 有不同的类型,j 番目 (1 \leqq j \leqq N) 盒子数量最多 C_j 足够大,可以塞满馒头,售价为 E_j 这是日元。这些 N 盒子有多少种类型(0 種類以上 N 类型如下) 1 我们决定把包子一个一个地订购,装进盒子里,然后成套出售。每个包子套餐的价格是其中包含的包子价格的总和。

如果所有包子套装都卖掉,IOI 能赚到的最大利润是多少?这里,利润是指售出的包子套餐总价减去订购的包子总价所得的值。注意,未装盒的包子将由IOI的员工享用,因此利润不会受到影响。

課題

给定每个馒头的价格以及每个盒子的尺寸和价格,编写一个程序来找出 IOI 公司可以获得的最大利润。


入力

从标准输入读取以下数据。

  • 1 行包含一个整数 M, N 是用空格作为分隔符,并且 manju 是 M 件、盒 N 表示有不同类型。
  • 继续 M 行 i 行目 (1 \leqq i \leqq M) 是一个整数 写入 P_i ,i 馒头的价格是 P_i 代表一个圆圈。
  • 继续 N 行 j 行目 (1 \leqq j \leqq N) 是一个整数 写入 C_j, E_j 以空格作为分隔符写入, 第j 个框最多为 它足够大,可以容纳 C_j 馒头,而且价格低廉。 E_j 代表一个圆圈。

出力

代表 IOI 可以获得的日元最大利润的整数被发送到标准输出。 输出为 1 行。


制限

所有输入数据满足以下条件。

  • 1 \leqq M \leqq 10\,000.
  • 1 \leqq N \leqq 500.
  • 1 \leqq P_i \leqq 10\,000 (1 \leqq i \leqq M).
  • 1 \leqq C_j \leqq 10\,000 (1 \leqq j \leqq N).
  • 1 \leqq E_j \leqq 10\,000 (1 \leqq j \leqq N).

小課題

小課題 1 [25 点]

N \leqq 10 很满意。

小課題 2 [35 点]

C_j \leqq 10 (1 \leqq j \leqq N)满意。

小課題 3 [40 点]

没有其他限制。


入力例 1

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

出力例 1

480

在此示例中,1 第一个盒子(100 日元)和 2 第一个盒子(120 日元),例如, 在第 1 框中 1 与 th 馒头 2 塞满了第一个包子 180 + 160 = 340 作为一组圆圈出售,2 框中 3 与 th 馒头 4 塞满了第一个包子 170 + 190 = 360 当以日元为单位出售时,IOI 的利润为 700 - 220 = 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