面包

题目描述

狐狸尼克制作了 $M$ 种口味互不相同的面包各一个，第 $i$ 个面包的售价为 $P_i$ 元。除此之外，他还有 $N$ 个包装盒，第 $j$ 个包装盒最多能装 $C_j$ 个面包，购买这个包装盒需要花费 $E_j$ 元。

尼克只能把一些面包装进盒子里打包出售，不能零售；也可以选择不出售某些面包。一个包装盒的利润等于盒内所有面包价格之和减去该包装盒的价格。你可以购买任意多个包装盒，并自行决定每个盒子里装哪些面包。请你求出最大可能利润。

数据范围

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

输入格式

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

$M$ $N$

$P_1$

$P_2$

$\vdots$

$P_M$

$C_1$ $E_1$

$C_2$ $E_2$

$\vdots$

$C_N$ $E_N$

其中：

• 第一行输入两个正整数 $M,N$，分别表示面包数量和包装盒数量。
• 接下来 $M$ 行，每行输入一个正整数 $P_i$，表示第 $i$ 个面包的价格。
• 接下来 $N$ 行，每行输入两个正整数 $C_j,E_j$，表示第 $j$ 个包装盒的容量和价格。

输出格式

输出一行一个整数，表示狐狸尼克能够获得的最大利润。

样例

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

480

2 2
1000
2000
1 6666
1 7777

0

样例解释

在样例 1 中，选择第 $1$ 个和第 $3$ 个包装盒最优：第一个包装盒装第 $1,4$ 个面包，利润为 $180+170-100=250$；第三个包装盒装第 $2,3$ 个面包，利润为 $160+190-120=230$；总利润为 $480$。在样例 2 中，最优策略是不购买任何包装盒，因此利润为 $0$。