Farmer John a récemment acheté une grange avec $N$ machines à traire ($1 \le N \le 40,000$), numérotées $1..N$ et alignées.

La machine $i$ extrait $M(i)$ unités par jour ($1 \le M(i) \le 100{,}000$). Trop proches, ses deux voisines ne peuvent fonctionner le jour où $i$ fonctionne (une seule voisine aux extrémités). Il peut choisir un sous-ensemble différent chaque jour.

Il veut le maximum total sur $D$ jours ($1 \le D \le 50,000$). Au début de chaque jour, il a le temps d'entretenir une machine choisie $i$, changeant son débit $M(i)$ à partir de ce jour. Calculez le maximum sur $D$ jours selon les modifications (il peut dépasser un entier de 32 bits).

Entrée

• Ligne 1 : $N$ et $D$.
• Lignes $2..1+N$ : la ligne $i+1$ donne le $M(i)$ initial.
• Lignes $2+N..1+N+D$ : la ligne $1+N+d$ donne les entiers $i$, $m$, changeant $M(i)$ en $m$ au début du jour $d$.

Sortie

• Ligne 1 : maximum total produit par FJ sur $D$ jours.

Exemples

Entrée 1

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

Sortie 1

32

Remarque

5 machines ont initialement 1,2,3,4,5. Au jour 1, la machine 5 passe à 2 unités, et ainsi de suite.

Jour 1 : optimum $2+4 = 6$ (aussi $1+3+2$). Jour 2 : $7+4 = 11$. Jour 3 : $10+3+2=15$.

Auteur du problème : Brian Dean