Farmer John compró recientemente un establo con $N$ máquinas de ordeño ($1 \le N \le 40,000$), numeradas $1..N$ y en fila.

La máquina $i$ extrae $M(i)$ unidades diarias ($1 \le M(i) \le 100{,}000$). Están demasiado cerca: si usa $i$, sus dos vecinas no pueden usarse ese día (en extremos solo una). Puede elegir subconjuntos distintos cada día.

Quiere el máximo total en $D$ días ($1 \le D \le 50,000$). Al inicio de cada día tiene tiempo de mantener una máquina elegida $i$, cambiando su producción $M(i)$ desde ese día en adelante. Calcula el máximo según las modificaciones (puede no caber en entero de 32 bits).

Entrada

• Línea 1: $N$ y $D$.
• Líneas $2..1+N$: la línea $i+1$ contiene $M(i)$ inicial.
• Líneas $2+N..1+N+D$: la línea $1+N+d$ tiene enteros $i$, $m$, que cambian $M(i)$ a $m$ al inicio del día $d$.

Salida

• Línea 1: máximo total de FJ en $D$ días.

Ejemplos

Entrada 1

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

Salida 1

32

Nota

5 máquinas inicialmente producen 1,2,3,4,5. El día 1 la máquina 5 cambia a 2 unidades, etc.

Día 1: óptimo $2+4 = 6$ (también $1+3+2$). Día 2: $7+4 = 11$. Día 3: $10+3+2=15$.

Autor del problema: Brian Dean