406957: GYM102625 C Matiyao Be Mid Sem hee toh hai

C. Matiyao Be Mid Sem hee toh haitime limit per test1 secondmemory limit per test1024 megabytesinputstandard inputoutputstandard 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

ExamplesInput

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