Farmer John comprou recentemente um celeiro com $N$ máquinas de ordenha ($1 \le N \le 40,000$), numeradas $1..N$ em fila.

Máquina $i$ extrai $M(i)$ unidades por dia ($1 \le M(i) \le 100{,}000$). Muito próximas, ambas vizinhas não podem ser usadas no dia em que $i$ funciona (nas pontas só uma). Pode escolher subconjuntos diferentes por dia.

Quer o máximo total em $D$ dias ($1 \le D \le 50,000$). No início de cada dia há tempo de manter uma máquina escolhida $i$, mudando sua produção $M(i)$ daquele dia em diante. Calcule o máximo pelas modificações (pode não caber em inteiro de 32 bits).

Entrada

• Linha 1: $N$ e $D$.
• Linhas $2..1+N$: linha $i+1$ contém $M(i)$ inicial.
• Linhas $2+N..1+N+D$: linha $1+N+d$ tem inteiros $i$, $m$, mudando $M(i)$ para $m$ no início do dia $d$.

Saída

• Linha 1: máximo total de FJ em $D$ dias.

Exemplos

Entrada 1

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

Saída 1

32

Nota

5 máquinas produzem inicialmente 1,2,3,4,5. No dia 1 a máquina 5 muda para 2 unidades, e assim por diante.

Dia 1: ótimo $2+4 = 6$ (também $1+3+2$). Dia 2: $7+4 = 11$. Dia 3: $10+3+2=15$.

Autor do problema: Brian Dean