Farmer John kupił nową stodołę z $N$ dojarkami ($1 \le N \le 40,000$), ponumerowanymi $1..N$ w rzędzie.

Maszyna $i$ daje dziennie $M(i)$ jednostek ($1 \le M(i) \le 100{,}000$). Są za blisko: przy użyciu $i$ obie sąsiednie nie mogą działać tego dnia (skrajne mają jednego sąsiada). Codziennie można wybierać inne podzbiory.

Chce maksimum łączne przez $D$ dni ($1 \le D \le 50,000$). Na początku dnia ma czas serwisować jedną wybraną $i$, zmieniając jej wydajność $M(i)$ od tego dnia dalej. Oblicz maksimum z listy zmian (może nie mieścić się w 32-bitowej liczbie całkowitej).

Wejście

• Wiersz 1: $N$ i $D$.
• Wiersze $2..1+N$: wiersz $i+1$ zawiera początkowe $M(i)$.
• Wiersze $2+N..1+N+D$: wiersz $1+N+d$ ma całkowite $i$, $m$, zmieniające $M(i)$ na $m$ na początku dnia $d$.

Wyjście

• Wiersz 1: maksymalny łączny udój FJ przez $D$ dni.

Przykład

Wejście 1

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

Wyjście 1

32

Uwagi

5 maszyn ma początkowo 1,2,3,4,5. Dnia 1 maszyna 5 zmienia się na 2 jednostki, itd.

Dzień 1: optimum $2+4 = 6$ (także $1+3+2$). Dzień 2: $7+4 = 11$. Dzień 3: $10+3+2=15$.

Autor zadania: Brian Dean