Problem H
Fishmongers
You fish fish.
You hate fish.
You love monies.
Therefore sell fish.
To fishmongers.
For maximum profit.
Input
The first line of input contains two integers $n$ ($1 \leq n \leq 100\, 000$), the number of fish you have to sell, and $m$ ($1 \leq m \leq 100\, 000$), the number of fishmongers. On the second line follows $n$ space-separated integers $w_1, w_2, \ldots , w_ n$, the weight of each of your fish in kilograms ($1 \leq w_ i \leq 100\, 000$). Finally, there are $m$ lines, the $j$’th of which consisting of two integers $x_ j$ ($1 \leq x_ j \leq 100\, 000$) and $p_ j$ ($1 \leq p_ j \leq 100\, 000$), 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.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 3 1 2 7 5 2 4 1 5 3 3 |
66 |
