题目描述

乔治有 $N$ 张卡片。

在第 $i$ 张卡片上写有一个整数 $A_i$。按照次序$j= 1,2,…,M$，你将执行以下操作之一：

操作:选取至多 $B_j$张卡片(可以是零张)。

将每张选取的卡片上的整数替换为$C_j$。

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

输入

第一行两个整数分别表示$N,M$

第二行$N$个整数,分别表示第$i$张卡片上的整数

接下来一共$M$行,每行分别是$B_i,C_i$

输出

输出执行了$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位整数类型中。

$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$