有 M种互不相同的馒头各一个,第 i 个馒头卖 Pi 元。
有 N 个包装盒,第 j 个包装盒最多能装 Cj 个馒头,买第 j 个包装盒的花费为 Ej 元。要求只能将一些馒头放进包装盒中打包出售,不能零售,当然也可以不出售某些馒头(卖剩的馒头被出题人吃了,出题人还吃得津津有味~)。售出一盒馒头得到的利润为盒内所有馒头的价格减去包装盒的价格。
现在买下(这 N 个包装盒)其中的一些包装盒(也可以不买,还可以全买),将馒头打包出售,求最大可能利润。
第一行两个正整数M , N ,意义如题目描述;
接下来M 行,每行一个正整数 Pi ,表示第 i 个馒头的价格;
接下来 N 行,每行两个正整数 Cj,Ej表示第 j 个包装盒最多能装 Cj 个馒头,花费 Ej 元。
一行一个整数,表示最大可能利润。
4 3
180
160
170
190
2 100
3 120
4 250
480
10 4 200 250 300 300 350 400 500 300 250 200 3 1400 2 500 2 600 1 900
输出
450