Fishmongers

Interview

Time limit1sMemory limit512 MB

Summary

Assign each fish to a fishmonger with a weight limit and per-kilogram price so total earnings are maximized.

Level: Medium5 of 10
Topics: Greedy, Sorting, Heap, Array
Solved: No attempts yet

Problem

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 \le n \le 100\,000$ ), the number of fish you have to sell, and $m$ ( $1 \le m \le 100\,000$ ), the number of fishmongers. The second line contains $n$ space-separated integers $w_1, w_2, \ldots, w_n$ , the weight of each of your fish in kilograms ( $1 \le w_i \le 100\,000$ ). Finally, there are $m$ lines, the $j$ 'th of which consists of two integers $x_j$ ( $1 \le x_j \le 100\,000$ ) and $p_j$ ( $1 \le p_j \le 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.

Examples1

Example 1
Input
```
4 3
1 2 7 5
2 4
1 5
3 3
```
Expected output
```
66
```