AT_joi2014ho2 IOI 饅頭 (IOI Manju)

Incredible Okashi Inc. 是一家生产“极其美味的点心（incredible okashi）”的公司。这里简称为 IOI 社。IOI 社制作了特制的 IOI 馒头，并决定将其出售。IOI 社制作了 $M$ 种不同的馒头，每种各 $1$ 个。制作出的 $M$ 个馒头大小相同，但每个口味不同，因此价格也各不相同，第 $i$ 个（$1 \leq i \leq M$）馒头的价格为 $P_i$ 日元。 顺便问一下，你知道 Just Odd Inventions 公司吗？这家公司的业务是“只是奇怪的发明（just odd inventions）”，这里简称为 JOI 社。IOI 社决定向 JOI 社订购用于装馒头的高级盒子。JOI 社生产的馒头盒有 $N$ 种，第 $j$ 种（$1 \leq j \leq N$）盒子最多可以装 $C_j$ 个馒头，售价为 $E_j$ 日元。在这 $N$ 种盒子中，可以选择任意种类（可以为 $0$ 种，也可以为 $N$ 种），每种最多订购 $1$ 个，并将馒头分装进这些盒子中作为套装进行销售。每个馒头套装的售价为其中所含馒头价格的总和。 假设所有馒头套装都能售出，IOI 社能够获得的最大利润是多少？这里的利润指的是售出馒头套装的总价格减去订购盒子的总价格。未装入盒子的馒头将由 IOI 社的员工享用，不计入利润。

从标准输入读取以下数据。 - 第 $1$ 行包含两个整数 $M,\ N$，用空格隔开，表示有 $M$ 个馒头，$N$ 种盒子。 - 接下来的 $M$ 行，第 $i$ 行（$1 \leq i \leq M$）包含一个整数 $P_i$，表示第 $i$ 个馒头的价格。 - 接下来的 $N$ 行，第 $j$ 行（$1 \leq j \leq N$）包含两个整数 $C_j,\ E_j$，用空格隔开，表示第 $j$ 个盒子最多可装 $C_j$ 个馒头，售价为 $E_j$ 日元。

请输出 IOI 社能够获得的最大利润（以日元为单位的整数），占一行。

## 任务 给定每个馒头的价格，以及每个盒子的容量和价格，编写程序求出 IOI 社能够获得的最大利润。 ## 限制 所有输入数据满足以下条件： - $1 \leq M \leq 10\,000$。 - $1 \leq N \leq 500$。 - $1 \leq P_i \leq 10\,000$（$1 \leq i \leq M$）。 - $1 \leq C_j \leq 10\,000$（$1 \leq j \leq N$）。 - $1 \leq E_j \leq 10\,000$（$1 \leq j \leq N$）。 ## 子任务 ### 子任务 1 [25 分] 满足 $N \leq 10$。 ### 子任务 2 [35 分] 满足 $C_j \leq 10$（$1 \leq j \leq N$）。 ### 子任务 3 [40 分] 无额外限制。 ## 样例解释 1 在此例中，订购第 $1$ 个盒子（$100$ 日元）和第 $2$ 个盒子（$120$ 日元），例如将第 $1$ 个盒子装入第 $1$ 个和第 $2$ 个馒头，作为 $180 + 160 = 340$ 日元的套装出售，将第 $2$ 个盒子装入第 $3$ 个和第 $4$ 个馒头，作为 $170 + 190 = 360$ 日元的套装出售，则 IOI 社的利润为 $700 - 220 = 480$ 日元。 ## 样例解释 2 - 由 ChatGPT 4.1 翻译