题意：

从前有$M$个$IOI$馒头（？？？）和$N$个箱子。

第$i$个馒头的卖价是$P_i$，第i个箱子的容量（可装馒头的数量）为$C_i$，价格是$E_i$。

你可以购买一些箱子，并往里面装入$IOI$馒头，但装入数量不能超过箱子的容量之和。这些$IOI$馒头将被出售并获得相应的钱数。

箱子不能重复买。问你最多能赚多少钱（允许啥都不买，此时收益为0）。

输入：第一行$M$,$N$。

接下来$M$行，一行一个$P_i$。

再接下来$N$行，一行两个数，$C_i$,$E_i$。

所有数据含义见题意。

输出：一行一个整数，表示能赚多少钱。

样例解释：

输入1：

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

输出：480

解释：买2和3的箱子，把所有馒头装进去，收益为180+160+170+190-100-120=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

个人解释：买容量2的两个箱子，装500,400,350,300，总产值为450。

数据范围：

$1\leq M\leq10000$

$1\leq N \leq 500$

$1\leq P_i,C_i,E_i \leq 10000$

感谢@I_am_wx 提供的翻译