IOI的利润

给定每个饅頭的价格以及每个箱子的大小和价格，求IOI公司能够获得的最大利润。

输入

从标准输入读取以下数据：

• 第一行包含两个整数 $M$ 和 $N$，用空格分隔，表示有 $M$ 个饅頭和 $N$ 种箱子。
• 接下来的 $M$ 行中的第 $i$ 行（$1 \leq i \leq M$）包含一个整数 $P_i$，表示第 $i$ 个饅頭的价格为 $P_i$ 元。
• 接下来的 $N$ 行中的第 $j$ 行（$1 \leq j \leq N$）包含两个整数 $C_j$ 和 $E_j$，由空格分隔，表示第 $j$ 种箱子可以装载最多 $C_j$ 个饅頭，价格为 $E_j$ 元。

输出

将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

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

输出示例 1

480

在这个例子中，IOI公司下订单第一个箱子（100元）和第二个箱子（120元）。例如，将第一个饅頭和第二个饅頭装进第一个箱子，以340元的价格销售。将第三个饅頭和第四个饅頭装进第二个箱子，以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