题目描述

译自 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

480

在本例中，我们选择第一、第二个包装盒，第一个包装盒装第 $1,2$ 个馒头，第二个包装盒装第 $3,4$ 个馒头。第一盒馒头的利润是 $180+160-100=240$ 元，第二盒馒头的利润是 $170+190-120=240$ 元，因此总利润为 $240+240=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\le M\le 10^4,1\le N\le 500,1\le P_i,C_j,E_j\le 10^4$。

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