题目描述

You have $N$ cards. On the $i$-th card, an integer $A_i$ is written.

For each $j = 1, 2, ..., M$ in this order, you will perform the following operation once:

Operation: Choose at most $B_j$ cards (possibly zero). Replace the integer written on each chosen card with $C_j$.

Find the maximum possible sum of the integers written on the $N$ cards after the $M$ operations.

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

对于这个顺序中的每一张 $j = 1, 2, ..., M$ ，你都要执行一次下面的操作：

操作：最多选择 $B_j$ 张纸牌（可能是零）。用 $C_j$ 替换写在每张所选卡片上的整数。

求经过 $M$ 运算后，写在 $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

样例输入 #1

3 2
5 1 4
2 3
1 5

样例输出 #1

14

样例 #2

样例输入 #2

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

样例输出 #2

338

样例 #3

样例输入 #3

3 2
100 100 100
3 99
3 99

样例输出 #3

300

样例 #4

样例输入 #4

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

样例输出 #4

10000000001

说明

数据规模与约定

• 所有输入值均为整数。
• $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$

样例 $1$ 解释

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

样例 $4$ 解释

输出可能不适合 $32$ （位）整数类型。