Problem Description

N God is a farmer who grows vegetables. He planted $n$ flowers, and each flower has an initial beauty value $a_i$. However, he found that $m$ weeds also grew in the garden, so N God decided to trim these weeds to make the flowers more beautiful.

It is known that the $i$-th weed grows between the $x_i$-th flower and the $(x_i+1)$-th flower, with beauty value $y_i$. N God can choose to trim this weed, or not trim it. If he chooses to trim it, he can trim it to the left, making the beauty value of the $x_i$-th flower become $y_i$. Or he can trim it to the right, making the beauty value of the $(x_i+1)$-th flower become $y_i$. Now, he wants to know the maximum possible sum of the flowers' beauty values after trimming.

Formally: Given a sequence $a$ of length $n$, there are $m$ operations. For each operation, two parameters $x_i, y_i$ are given. You can skip this operation, or choose to perform one of the following assignments:

• Assign $a_{x_i}$ to $y_i$.

• Assign $a_{x_i+1}$ to $y_i$.

Find the maximum possible sum of the sequence elements after the $m$ operations.

Input Format

The first line contains two integers $n, m$.

The second line contains $n$ integers, representing the sequence $a$.

The next $m$ lines each contain two integers $x_i, y_i$.

Output Format

Output one integer, representing the maximum possible sum of the flowers' beauty values after trimming.

3 3
2 1 4
1 3
2 4
1 1

11

5 8
3 1 5 2 3
1 2
1 4
2 5
2 4
3 7
3 6
4 4
4 10

32

12 9
1 1 1 2 1 1 1 1 1 2 2 1
1 2
1 2
2 2
5 2
5 2
6 1
8 2
8 2
10 2

22

7 15
1 7 14 1 9 4 18
1 10
3 6
2 6
3 20
2 12
5 16
4 7
3 17
2 6
1 23
2 12
4 16
3 14
5 12
5 20

126

Hint

Explanation for Sample 1: In the first trimming, trim the left flower and assign $a_1$ to $3$. In the second trimming, trim the left flower and assign $a_2$ to $4$. The third operation is skipped. The sum of $a$ is $3+4+4=11$, and it can be proven that this is the optimal plan.

For all testdata, $1\leq a_i,y_i\leq 2000, 1 \le x_i< n$, $2 \leq n\leq2\times 10^5$, $1 \leq m\leq10^6$.

Constraints table:

Special Property A: $m=2n-2$. For the $i$-th operation among the $m$ operations, $x_i=\lceil \frac{i}{2}\rceil$.

Special Property B: $a_i,y_i\leq 2$.

Translated by ChatGPT 5