面包

题目描述:

由于蛋糕店的生意越来越红火，狐狸尼克也想添加一些其它的种类，比如面包类的等。

狐狸尼克制作了 M 种口味互不相同的面包各一个，第 i ( 1 <= i <= M )个面包卖P_i元。

狐狸尼克有N个包装盒，第 j ( 1 <= j <= N )个包装盒最多能装 C_j 个面包，买第j个包装盒需要花费 E_j 元。要求只能将一些面包放进包装盒中打包出售，不能零售。当然也可以不出售某些面包(卖剩下的面包狐狸尼克就会免费送给食客们品尝)。售出一盒面包得到的利润为盒内所有面包的价格总和减去包装盒的价格。

现在买下(这 N 个包装盒)其中的一些包装盒(也可以不买，还可以全买)，将面包打包装到包装盒中出售，求最大可能的利润。

输入格式:

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

接下来 M 行，每行一个正整数P_i ，表示第 i 个面包的价格。

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

输出格式:

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

数据范围:

1 <= M <= 10⁴ ； 1 <= N <= 500； 1 <= P_i, C_j, E_j <= 10⁴

样例输入:

样例1：
4 3
180
160
190
170
2 100
4 250
3 120

样例2：
2 2
1000
2000
1 6666
1 7777

样例输出:

样例1：
480

样例2：
0

提示:

【样例1解释】

在本例中，我们选择第一、第三个包装盒。第一个包装盒装第 1, 4个面包，其利润是 180 + 170 - 100 = 250 元。第三个包装盒装第 2 , 3 个面包，其利润是160 + 190 - 120 = 230 元。因此总利润为  250 + 230 = 480 元。

【样例2解释】

在本例中，为了最大化利益，最好不买包装盒(也就是不卖面包，都免费送给食客们品尝)。

时间限制: 1000ms
空间限制: 256MB

---

来源: 温州市计算机学会2023比赛