题目描述

译自 JOI 2014 Final T2「IOI 饅頭」

有 $M$ 种互不相同的馒头各一个，第 $i$ 个馒头卖 $P_i$ 元。

有 $N$ 个包装盒，第 $j$ 个包装盒最多能装 $C_j$ 个馒头，买第 $j$ 个包装盒的花费为 $E_j$ 元。要求只能将一些馒头放进包装盒中打包出售，不能零售，当然也可以不出售某些馒头（卖剩的馒头被出题人吃了，出题人还吃得津津有味~）。售出一盒馒头得到的利润为盒内所有馒头的价格减去包装盒的价格。

现在买下（这 $N$ 个包装盒）其中的一些包装盒（也可以不买，还可以全买），将馒头打包出售，求最大可能利润。

输入格式

第一行两个正整数 $M,N$，意义如题目描述；

接下来 $M$ 行，每行一个正整数 $P_i$，表示第 $i$ 个馒头的价格；

接下来 $N$ 行，每行两个正整数 $C_j,E_j$，表示第 $j$ 个包装盒最多能装 $C_j$ 个馒头，花费 $E_j$ 元。

输出格式

一行一个整数，表示最大可能利润。

输入输出样例

输入 #1

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

输出 #1

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

数据范围与提示

对于全部数据，$1\le M\le 10^4,1\le N\le 500,1\le P_i,C_j,E_j\le 10^4$。

详细子任务及数据满足条件如下表：

\begin{array}{|c|c|c|} \hline Subtask & \textbf{追加限制} & \textbf{分值} \\ \hline 1 & N\le 10 & 25 \\ \hline 2 & C_j\le 10 & 35 \\ \hline 3 & \textbf{无追加限制} & 40 \\ \hline \end{array}