Farmer John ha comprato una stalla con $N$ mungitrici ($1 \le N \le 40,000$), numerate $1..N$ in fila.

Macchina $i$ estrae $M(i)$ unità al giorno ($1 \le M(i) \le 100{,}000$). Troppo vicine: usando $i$, le due adiacenti non possono funzionare quel giorno (agli estremi solo una). Può scegliere sottoinsiemi diversi ogni giorno.

Vuole il massimo totale in $D$ giorni ($1 \le D \le 50,000$). All'inizio di ogni giorno può mantenere una macchina scelta $i$, cambiando la produzione $M(i)$ da quel giorno in poi. Calcola il massimo dalle modifiche (potrebbe non entrare in intero a 32 bit).

Input

• Riga 1: $N$ e $D$.
• Righe $2..1+N$: riga $i+1$ contiene $M(i)$ iniziale.
• Righe $2+N..1+N+D$: riga $1+N+d$ contiene interi $i$, $m$, per cambiare $M(i)$ in $m$ all'inizio del giorno $d$.

Output

• Riga 1: massimo totale di FJ in $D$ giorni.

Esempi

Input 1

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

Output 1

32

Spiegazione

5 macchine inizialmente producono 1,2,3,4,5. Giorno 1 cambia la macchina 5 a 2 unità, e così via.

Giorno 1: ottimo $2+4 = 6$ (anche $1+3+2$). Giorno 2: $7+4 = 11$. Giorno 3: $10+3+2=15$.

Autore del problema: Brian Dean