Integer Cards

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.

Examples

Input

3 2 5 1 4 2 3 1 5

Output

14

Input

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

Output

338

Input

3 2 100 100 100 3 99 3 99

Output

300

Input

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

Output

10000000001

inputFormat

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

outputFormat

Output

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

Examples

Input

3 2 5 1 4 2 3 1 5

Output

14

Input

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

Output

338

Input

3 2 100 100 100 3 99 3 99

Output

300

Input

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

Output

10000000001

样例

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

338