P15812 [JOI 2014 Final] IOI 馒头 / IOI Manju

Incredible Okashi Inc. 是一家制作“不可思议的美味点心 (incredible okashi)”的公司。以下简称 IOI 社。IOI 社 制作了特制的 IOI 馒头，并决定将其出售。IOI 社 制作了 $M$ 种馒头，每种一个。制作出的 $M$ 个馒头大小相同，但味道各异，因此价格各不相同，第 $i$ 个 ($1 \le i \le M$) 馒头的价格为 $P_i$ 日元。 话说回来，你知道 Just Odd Inventions 公司吗？这家公司的业务是进行“仅仅是奇妙的发明 (just odd inventions)”。以下简称 JOI 社。IOI 社决定向 JOI 社订购用于装馒头的豪华盒子。JOI 社 制作的馒头用盒子有 $N$ 种，第 $j$ 种 ($1 \le j \le N$) 盒子最多能装 $C_j$ 个馒头，其售价为 $E_j$ 日元。IOI 社决定订购这 $N$ 种盒子中的若干种（0 种以上 $N$ 种以下），每种一个，然后将馒头分装到这些盒子里作为套装出售。每个馒头套装的价格等于其中所装馒头价格的总和。 假设所有馒头套装都能售出，IOI 社能够获得的最大利润是多少？这里利润是指售出的所有馒头套装价格总和减去订购的所有盒子价格总和。另外，对于没有装入盒子的馒头，将由 IOI 社的员工美味地享用，因此不影响利润。 ### 任务 给定每个馒头的价格，以及每种盒子的容量和价格，编写程序求出 IOI 社能够获得的最大利润。

从标准输入读取以下数据。 - 第 1 行包含以空格分隔的整数 $M, N$，表示有 $M$ 个馒头和 $N$ 种盒子。 - 接下来 $M$ 行中的第 $i$ 行 ($1 \le i \le M$) 包含整数 $P_i$，表示第 $i$ 个馒头的价格为 $P_i$ 日元。 - 接下来 $N$ 行中的第 $j$ 行 ($1 \le j \le N$) 包含以空格分隔的整数 $C_j, E_j$，表示第 $j$ 种盒子最多能装 $C_j$ 个馒头，其价格为 $E_j$ 日元。

向标准输出输出一行，包含一个整数，表示 IOI 社能获得的最大利润（单位：日元）。

### 样例解释 1 在此样例中，订购第 1 种盒子（$100$ 日元）和第 2 种盒子 ($120$ 日元)。例如，将第 1 个和第 2 个馒头装入第 1 个盒子，作为 $180 + 160 = 340$ 日元的套装出售；将第 3 个和第 4 个馒头装入第 2 个盒子，作为 $170 + 190 = 360$ 日元的套装出售。则 IOI 社的利润为 $700 - 220 = 480$ 日元。 ### 样例解释 2 在此样例中，为了最大化利润，最好完全不购买任何盒子。 ### 数据范围 所有输入数据满足以下条件。 - $1 \le M \le 10000$ - $1 \le N \le 500$ - $1 \le P_i \le 10000$ ($1 \le i \le M$) - $1 \le C_j \le 10000$ ($1 \le j \le N$) - $1 \le E_j \le 10000$ ($1 \le j \le N$) ### 子任务 #### 子任务 1 [25 分] 满足 $N \le 10$。 #### 子任务 2 [35 分] 满足 $C_j \le 10$ ($1 \le j \le N$)。 #### 子任务 3 [40 分] 没有额外限制。 --- 翻译由 DeepSeek V3.2 完成