C. Matiyao Be Mid Sem hee toh hai
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

'MID SEM HAI BE MATIYAO', This famous line brought trouble to lots of students in this Semester due to the Covid-19 outbreak.

So, one such student approached his HoD for help. He gave him $$$N$$$, the number of subjects and his marks in each subject, $$$A_i$$$ . The HoD gives him the right to perform the following operation once for every $$$j$$$ = 1 to $$$j$$$ = $$$M$$$ in order, :

Operation: Choose at most $$$B_j$$$ subjects (possibly zero) and replace marks of those subjects to $$$C_j$$$.

Now, he wants to maximize the sum of marks of all the subjects.

As you all know he has done nothing except 'matiyana', in this semester. So he approached you to tell him the maximum sum of the marks of all the subjects, he can get.

Input

The first line contains two integers $$$N$$$, $$$M$$$ (1 $$$\leq$$$ $$$N$$$ , $$$M$$$ $$$\leq$$$ $$$10^5$$$), separated by a space — the number of subjects and the number of operations.

The second line contains $$$N$$$ integers $$$A_i$$$ (1 $$$\leq$$$ $$$A_i$$$ $$$\leq$$$ $$$10^9$$$) separated by spaces — marks in each subject.

The next $$$M$$$ line contain two integers $$$B_j$$$ and $$$C_j$$$ separated by space (1 $$$\leq$$$ $$$B_j$$$ $$$\leq$$$ $$$N$$$, 1 $$$\leq$$$ $$$C_j$$$ $$$\leq$$$ $$$10^9$$$)

Output

Print the maximum possible sum of the marks of all the $$$N$$$ subjects after performing the $$$M$$$ operations

Examples
Input
3 2
5 1 4
2 3
1 5
Output
14
Input
10 3
1 8 5 7 100 4 52 33 13 5
3 10
4 30
1 4
Output
338
Input
3 2
100 100 100
3 99
3 99
Output
300
Input
11 3
1 1 1 1 1 1 1 1 1 1 1
3 1000000000
4 1000000000
3 1000000000
Output
10000000001
Note

In $$$1^{st}$$$ test case, we perform the 2 operations as follows :

a. Choose 0 subjects for the first operation i.e. Don't replace marks in any subject by 3.

b. For the second operation, replace the marks of the $$$2^{nd}$$$ subject by 5

In this way, the sum of the marks of the three subjects becomes 5 + 5 + 4 = 14, which is the maximum result possible.

Lesson : MID SEM MEIN BHI PADH LO THODA