D - 整数卡片

得分：400 分

问题描述

你有 $N$ 张卡片。在第 $i$ 张卡片上写有一个整数 $A_i$。

按照次序 $j = 1, 2, ..., M$，你将执行以下操作之一：

操作：选取至多 $B_j$ 张卡片（可以是零张）。将每张选取的卡片上的整数替换为 $C_j$。

求在执行完 $M$ 次操作后，$N$ 张卡片上整数的最大可能的和。

约束

• 输入中的所有值均为整数。
• $1 \leq N \leq 10^5$
• $1 \leq M \leq 10^5$
• $1 \leq A_i, C_i \leq 10^9$
• $1 \leq B_i \leq N$

输入

从标准输入读入输入数据，格式如下：

$N$ $M$

$A_1$ $A_2$ $...$ $A_N$

$B_1$ $C_1$

$B_2$ $C_2$

$\vdots$

$B_M$ $C_M$

输出

打印在执行完 $M$ 次操作后，$N$ 张卡片上整数的最大可能的和。

3 2
5 1 4
2 3
1 5

14

将第二张卡片上的整数替换为 $5$，这样三张卡片上的整数之和为 $5 + 5 + 4 = 14$，这是最大的结果。

10 3
1 8 5 7 100 4 52 33 13 5
3 10
4 30
1 4

338

3 2
100 100 100
3 99
3 99

300

11 3
1 1 1 1 1 1 1 1 1 1 1
3 1000000000
4 1000000000
3 1000000000

10000000001

输出可能无法放入 $32$ 位整数类型中。