题目描述

有 $M$ 个馒头，其中第 $i$ 个馒头的价格为 $P_i$ 元。

有 $N$ 种装馒头的盒子，第 $i$ 种盒子最多能装 $C_i$ 个馒头，其售价为 $E_i$ 元。现在决定订购这 $N$ 种盒子中的若干种（$0$ 种以上 $N$ 种以下），然后将馒头分装到这些盒子里作为套装出售。每个馒头套装的价格等于其中所装馒头价格的总和。

假设所有馒头套装都能售出，能够获得的最大利润是多少？这里利润是指售出的所有馒头套装价格总和减去订购的所有盒子价格总和。另外，对于没有装入盒子的馒头，不会影响利润。

输入格式

第 $1$ 行包含以空格分隔的整数 $M, N$，表示有 $M$ 个馒头和 $N$ 种盒子。

接下来 $M$ 行中的第 $i$ 行包含整数 $P_i$，表示第 $i$ 个馒头的价格为 $P_i$ 元。

接下来 $N$ 行中的第 $i$ 行包含以空格分隔的整数 $C_i, E_i$，表示第 $i$ 种盒子最多能装 $C_i$ 个馒头，其价格为 $E_i$ 元。

输出格式

输出一行，包含一个整数，表示能获得的最大利润。

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

480

2 2
1000
2000
1 6666
1 7777

0

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

450

提示

样例 1 解释

在此样例中，订购第 1 种盒子（$100$ 元）和第 2 种盒子 ($120$ 元)。例如，将第 1 个和第 2 个馒头装入第 1 个盒子，作为 $180 + 160 = 340$ 元的套装出售；将第 3 个和第 4 个馒头装入第 2 个盒子，作为 $170 + 190 = 360$ 元的套装出售。则利润为 $700 - 220 = 480$ 元。

样例 2 解释

在此样例中，为了最大化利润，最好完全不购买任何盒子。

数据范围

对于 $100\%$ 的数据满足：$1 \le M \le 10000$，$1 \le N \le 500$，$1 \le P_i,C_i,E_i \le 10000$。

• 子任务 $1$（$25$ 分）：满足 $N \le 10$。
• 子任务 $2$（$35$ 分）：满足 $C_i \le 10$。
• 子任务 $3$（$40$ 分）：没有额外限制。