2018-11-10 01:00 AKST

Bergen Open 2018


2018-11-10 06:00 AKST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -802 days 15:46:28

Time elapsed


Time remaining


Problem F

You fish fish.

You hate fish.

You love monies.

Therefore sell fish.

To fishmongers.

For maximum profit.


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.


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