Problem Statement

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.

Constraints

• All values in input are integers.
• $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$

Input

Input is given from Standard Input in the following format:

N M
A_1 A_2 ... A_N
B_1 C_1
B_2 C_2
\vdots
B_M C_M

Output

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