P16956 "NLOI Round1" Vacuum Sword Saint.

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.

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 one integer, representing the maximum possible sum of the flowers' beauty values after trimming.

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: Data Point ID|Score|$n\leq$|$m\leq$|Special Property| |---|---|---|---|---| $1$|$16$|$2\times 10^5$|$20$|None| $2$|$20$|$20$|$10^6$|None| $3$|$12$|$50$|$100$|None| $4$|$24$|$2\times 10^5$|$10^6$|A| $5$|$20$|$2\times 10^5$|$10^6$|B| $6$|$8$|$2\times 10^5$|$10^6$|None| 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