Background

Special for beginners, ^_^

Description

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

你接下来将要进行 $M$ 次操作：

第 $j$ 次操作有两个参数 $B_j$ 和 $C_j$ ，表示这次操作你要选择最多 $B_j$ 张卡片（可以选0张），将选出卡片上的整数改成 $C_j$ 。

$M$ 次操作结束后，$N$ 张卡片上的整数之和的最大值是多少？

Format

Input

第1行，2个正整数 $N,M（\le10^5）$。

第2行，$N$ 个正整数 $A_1, A_2, ⋯, A_N（\le10^9）$。

接下来 $M$ 行，每行两个正整数 $B_j , C_j（\le10^9）$。

Output

输出 $M$ 次操作后所有卡片上整数总和的最大值。

Samples

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

338

Limitation

1s, 1024KiB for each test case.