配点: 100 点
Incredible Okashi Inc. 是一家生产“incredible okashi”的公司。我们这里将其简称为IOI公司。 IOI公司制作了一款特殊的IOI馒头,所以他们决定出售它。 IOI 是 M 不同类型的包子 1 我一一做了。制作 M 馒头的大小都是一样的,但是每一个的口味不同,所以价格也不同。i 番目 (1 \leqq i \leqq M) 处的面包价格为 P_i 这是一个圆圈。
顺便问一下,你听说过 Just Odd Inventions 吗?这家公司的业务就是制造“只是奇怪的发明”。在这里,我们将其缩写为JOI。 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