NC53178. IOI 馒头
描述
译自 JOI 2014 Final T2「IOI 饅頭」
有M种互不相同的馒头各一个，第i个馒头卖
元。
有N个包装盒，第j个包装盒最多能装
个馒头，买第j个包装盒的花费为
元。要求只能将一些馒头放进包装盒中打包出售，不能零售，当然也可以不出售某些馒头（卖剩的馒头被出题人吃了，出题人还吃得津津有味~）。售出一盒馒头得到的利润为盒内所有馒头的价格减去包装盒的价格。
现在买下（这N个包装盒）其中的一些包装盒（也可以不买，还可以全买），将馒头打包出售，求最大可能利润。
有N个包装盒，第j个包装盒最多能装
现在买下（这N个包装盒）其中的一些包装盒（也可以不买，还可以全买），将馒头打包出售，求最大可能利润。
输入描述
第一行两个正整数M,N，意义如题目描述；
接下来M行，每行一个正整数
接下来N行，每行两个正整数，表示第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 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