题目描述

有 $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

输出

480

解释：选择第一、第二个包装盒，第一个包装盒装第 1,2 个馒头，第二个包装盒装第 3,4 个馒头。第一盒利润是 $180+160-100=240$ 元，第二盒利润是 $170+190-120=240$ 元，总利润为 $240+240=480$ 元。

样例 2

输入

2 2
1000
2000
1 6666
1 7777

输出

0

解释：为了最大化利益，最好不买包装盒（不卖馒头）。

样例 3

输入

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

输出

450

数据范围与提示

对于全部数据：

• $1 \le M \le 10^4$
• $1 \le N \le 500$
• $1 \le P_i, C_j, E_j \le 10^4$

子任务

Subtask	追加限制	分值
1	$N \le 10$	25
2	$C_j \le 10$	35
3	无追加限制	40