시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 0 0 0 0.000%

문제

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 w1, w2, . . . , wn, the weight of each of your fish in kilograms (1 ≤ wi ≤ 100 000). Finally, there are m lines, the j’th of which consisting of two integers xj (1 ≤ xj ≤ 100 000) and pj (1 ≤ pj ≤ 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.

예제 입력 1

4 3
1 2 7 5
2 4
1 5
3 3

예제 출력 1

66