Hide

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

Please log in to submit a solution to this problem

Log in