17906번 - Fishmongers 다국어

문제

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 ≤ n ≤ 100 000), the number of fish you have to sell, and m (1 ≤ m ≤ 100 000), the number of fishmongers. On the second line follows n space-separated integers w₁, w₂, . . . , w_n, the weight of each of your fish in kilograms (1 ≤ w_i ≤ 100 000). Finally, there are m lines, the j’th of which consisting of two integers x_j (1 ≤ x_j ≤ 100 000) and p_j (1 ≤ p_j ≤ 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.

제한

힌트