Problem D
Fishmongers

CC0, by Geir Fløde via Pixabay

Input

The first line of input contains two integers $n$ ($1\le n\le 100000$), the number of fish you have to sell, and $m$ ($1\le m\le 100000$), the number of fishmongers. On the second line follows $n$ space-separated integers $w_1,w_2,\dots ,w_n$, the weight of each of your fish in kilograms ($1\le w_i\le 100000$). Finally, there are $m$ lines, the $j$’th of which consisting of two integers $x_j$ ($1\le x_j\le 100000$) and $p_j$ ($1\le p_j\le 100000$), respectively indicating how many fish the $j$’th fishmonger wants to buy and how many monies he will pay per kilogram.

Output

A single integer, the maximum number of monies you can obtain by selling your fish to the fishmongers.

4 3
1 2 7 5
2 4
1 5
3 3

66