Incredible Okashi Inc. 是一家制作“极其美味的点心 (incredible okashi)”的公司，简称为 IOI 社。IOI 社制作了特制的 IOI 馒头，并决定将其出售。IOI 社制作了 $M$ 种馒头，每种各 1 个。这 $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 社决定订购这些礼盒中的若干种（0 种到 $N$ 种），每种礼盒各订购 1 个，并将馒头分装到这些礼盒中作为套装出售。每个馒头套装的价格为其所包含馒头的价格总和。

假设所有的馒头套装都能卖出，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 \le M \le 10\,000$
• $1 \le N \le 500$
• $1 \le P_i \le 10\,000$ ($1 \le i \le M$)
• $1 \le C_j \le 10\,000$ ($1 \le j \le N$)
• $1 \le E_j \le 10\,000$ ($1 \le j \le N$)

子任务

• 子任务 1 [25 点]：满足 $N \le 10$。
• 子任务 2 [35 点]：满足 $C_j \le 10$ ($1 \le j \le N$)。
• 子任务 3 [40 点]：无额外限制。

样例

样例输入 1

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

样例输出 1

480

说明 1

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

样例输入 2

2 2
1000
2000
1 6666
1 7777

样例输出 2

0

说明 2

在此例中，为了使利润最大化，最好一个礼盒也不买。

样例输入 3

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

样例输出 3

450