Farmer John kaufte kürzlich eine Scheune mit $N$ Melkmaschinen ($1 \le N \le 40,000$), nummeriert $1..N$ in einer Reihe.

Maschine $i$ liefert täglich $M(i)$ Einheiten ($1 \le M(i) \le 100{,}000$). Sie stehen zu eng: Wenn $i$ läuft, dürfen beide Nachbarn an diesem Tag nicht laufen (am Ende nur einer). Täglich darf er andere Teilmengen wählen.

Gesucht ist das maximale Gesamtvolumen über $D$ Tage ($1 \le D \le 50,000$). Zu Tagesbeginn kann er eine gewählte Maschine $i$ warten und ihre Tagesleistung $M(i)$ ab dann ändern. Berechne den Höchstwert gemäß Änderungen (er passt eventuell nicht in eine 32-Bit-Ganzzahl).

Eingabe

• Zeile 1: $N$ und $D$.
• Zeilen $2..1+N$: Zeile $i+1$ enthält anfangs $M(i)$.
• Zeilen $2+N..1+N+D$: Zeile $1+N+d$ enthält ganze $i$, $m$, um zu Beginn des Tages $d$ den Wert $M(i)$ auf $m$ zu ändern.

Ausgabe

• Zeile 1: FJs maximales Gesamtvolumen über $D$ Tage.

Beispiele

Eingabe 1

5 3
1
2
3
4
5
5 2
2 7
1 10

Ausgabe 1

32

Hinweis

5 Maschinen liefern anfangs 1,2,3,4,5. Am Tag 1 wird Maschine 5 auf 2 Einheiten geändert und so weiter.

Tag 1: Optimum $2+4 = 6$ (auch $1+3+2$). Tag 2: $7+4 = 11$. Tag 3: $10+3+2=15$.

Aufgabenautor: Brian Dean