题目描述

问题陈述

你有 $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$ 张卡片上写的整数的最大可能和。

示例输入 1

3 2
5 1 4
2 3
1 5

示例输出 1

14

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

示例输入 2

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

示例输出 2

338

示例输入 3

3 2
100 100 100
3 99
3 99

示例输出 3

300

示例输入 4

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

示例输出 4

10000000001

输出可能超过 $32$ 位整数类型的表示范围。