410491: GYM104027 D 饱了没红包

  随着信息化时代的发展，外卖业务成为了一片新蓝海。其中，饱了没是一支刚刚起步的新秀，为了开拓市场业务，饱了没发放了非常多的红包...

  Sleep很喜欢点外卖，再他了解到饱了没之后，只恨没有早点发现这个平台，白白损失很多大米。自此，他非常热衷于收集饱了没的各类满减红包。现在他已经选好了一些订单，并且希望在结算的时候花掉一部分满减红包，使自己尽可能少的花钱。显然，每个红包只能在至多一个订单结算中使用(当然也可以不被使用)，每个订单结算的时候只能使用至多一个红包(当然也可以不使用)。在这种情况下，Sleep想知道他最少需要花费多少钱。

  满减红包是在满足满减金额要求的时候获得满减红包面额的优惠。比如$$$50$$$元的待支付订单，可以使用满$$$50$$$减$$$20$$$的红包，然后该订单仅需支付$$$30$$$元，但是该订单不能使用满$$$60$$$减$$$30$$$的红包。

  第一行两个正整数$$$n,m$$$表示有$$$n$$$个待结算订单$$$m$$$个饱了没红包($$$1\leq n,m \leq 10^5$$$)

  第二行$$$n$$$个正整数$$$w$$$，$$$w_i$$$表示第$$$i$$$个待结算订单的金额。($$$ 1\leq w_i \leq 10^5$$$)

  接下来$$$m$$$行，每行两个正整数$$$x,y$$$表示，该满减红包是满$$$x$$$减$$$y$$$的红包。($$$1\leq y \leq x \leq 10^5$$$)

  输出一个正整数$$$Val$$$，表示最小花费的金额。

5 2
1 2 3 4 5
2 1
3 2

12