410491: GYM104027 D 饱了没红包

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

D. 饱了没红包time limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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

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

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

Input

  第一行两个正整数$$$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$$$)

Output

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

ExampleInput
5 2
1 2 3 4 5
2 1
3 2
Output
12

加入题单

上一题 下一题 算法标签: