Optimal Milking

Farmer John's new barn holds $N$ milking machines standing in a row, numbered $1$ through $N$ from the left.

Machine $i$ extracts $M(i)$ units of milk per day. The machines sit so close together that if machine $i$ runs on a given day, neither of its neighbors can run that day. A machine at either end has only one neighbor. Farmer John may choose a different set of machines to run on each day.

Farmer John wants the largest total amount of milk he can extract over $D$ days. At the start of each day he has time to service one machine, and that machine's daily output $M(i)$ changes from that day onward. Given the list of daily changes, report the maximum total milk over the $D$ days. The answer can exceed a 32-bit integer.

$1 \le N \le 40000$, $1 \le M(i) \le 100000$, and $1 \le D \le 50000$.

The first line contains $N$ and $D$.

Each of the next $N$ lines gives one initial value, with line $i$ holding $M(i)$.

Each of the following $D$ lines contains two integers $i$ and $m$. Line $d$ means Farmer John sets $M(i)$ to $m$ at the start of day $d$.

Print the maximum total amount of milk Farmer John can produce over the $D$ days.

Suppose five machines start with outputs 1, 2, 3, 4, 5 and machine 5 drops to 2 on the morning of day one.

Day one is best at $2 + 4 = 6$, and $1 + 3 + 2$ reaches 6 as well. If machine 2 then rises to 7, day two is $7 + 4 = 11$, and if machine 1 rises to 10, day three is $10 + 3 + 2 = 15$.