F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Problem 4977. -- [[Lydsy1708月赛]跳伞求生

4977: [[Lydsy1708月赛]跳伞求生

Time Limit: 5 Sec  Memory Limit: 256 MB
Submit: 592  Solved: 206
[Submit][Status][Discuss]

Description

小Q最近沉迷于《跳伞求生》游戏。他组建了一支由n名玩家(包括他自己)组成的战队,编号依次为1到n。这个游
戏中,每局游戏开始时,所有玩家都会从飞机上跳伞,选择一个目的地降落,跳伞和降落的时间有早有晚。在某局
游戏降落前,他们在空中观察发现地面上一共有m间房子,编号依次为1到m。其中每间房子恰好有一名敌人早于他
们到达。小Q战队的第i名玩家拥有a_i发子弹,地面上第i间房子里的敌人拥有b_i发子弹,消灭他可以获得c_i点积
分。每名玩家必须且只能选择一间房子降落,然后去消灭里面的敌人。若第i名玩家选择了第j间房子,如果a_i>b_
j,那么他就可以消灭该敌人,获得a_i-b_j+c_j的团队奖励积分,否则他会被敌人消灭。为了防止团灭,小Q不允
许多名玩家选择同一间房子,因此如果某位玩家毫无利用价值,你可以选择让他退出游戏。因为房子之间的距离过
长,你可以认为每名玩家在降落之后不能再去消灭其它房间里的敌人。作为小Q战队的指挥,请制定一套最优的降
落方案,使得最后获得的团队奖励总积分最大

Input

第一行包含两个正整数n,m(1<=n,m<=100000),分别表示战队的玩家数和地面上的房间数。
第二行包含n个正整数a_1,a_2,...,a_n(1<=a_i<=100000),分别表示每个玩家的子弹数。
接下来m行,每行两个正整数b_i,c_i(1<=b_i,c_i<=100000),分别表示每个敌人的子弹数和奖励积分。

Output

输出一行一个整数,即最后获得的团队奖励总积分的最大值。

Sample Input

3 3
4 4 4
2 3
1 3
5 3

Sample Output

11

HINT

Source

claris原创,本oj版权所有,翻版必究

[Submit][Status][Discuss]

HOME Back