You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

众所周知，每次做练习后，刘老师会给同学们相应的评语：愚蠢的人类， 聪明的土拨鼠。

在收到评语后， 同学们会改变学习状态，当然，有的学生受到鼓舞后，战斗值会增强，有的学生受到刺激后，战斗值会减弱。

题目详情 - Two Arrays And Swaps - ACjudge

做完该题后, 你可能会受到启发.

题目描述

北辰培训营里有$n$名同学，每位同学都有一个战斗值$a_i$。

今天的训练环节是完成$m$道练习题。

在做完第$i$题后，刘老师会最多选择$b_i$名同学(可以一个都不选)给出评价$c_i$，所有被选中的同学的战斗力会变为$c_i$。

刘老师想知道在 $m$ 次练习后，所有同学们的战斗力之和最大是多少？

数据格式

输入格式

第一行两个整数 $n, m$

第二行 $n$ 个整数$a_i$, 表示最开始每个同学的战斗值

接下来 $m$ 行，每行两个整数 $b_i, c_i$ ，表示第$i$次练习后, 刘老师可以进行的操作.

输出格式

一个整数，表示所有同学们的战斗值之和的最大值.

样例

样例1

3 2
1 5 4
1 5
2 3

14

样例1解释

在第$1$次练习后, 刘老师可以对第$1$个同学进行鼓舞, 使得战斗值提升至$5$, 第$2$次练习后不做任何处理

最终所有同学的战斗值为{5, 5, 4}, 总和为14

样例2

3 2
100 100 100
3 99
3 99

300

数据范围

$1 \le n,m \le 10^5,1 \le a_{i},c{i} \le 10^9,1 \le b_{i} \le n$