406957: GYM102625 C Matiyao Be Mid Sem hee toh hai

'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.

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$$$)

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

3 2
5 1 4
2 3
1 5

14

10 3
1 8 5 7 100 4 52 33 13 5
3 10
4 30
1 4

338

3 2
100 100 100
3 99
3 99

300

11 3
1 1 1 1 1 1 1 1 1 1 1
3 1000000000
4 1000000000
3 1000000000

10000000001

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