Bergen Open 2018

Start

2018-11-10 10:00 UTC

Bergen Open 2018

End

2018-11-10 15:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -282 days 10:52:15

5:00:00

0:00:00

Problem FFishmongers

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