Farmer John недавно купил сарай с $N$ доильными машинами ($1 \le N \le 40,000$), пронумерованными $1..N$ и стоящими в ряд.

Машина $i$ даёт $M(i)$ единиц молока в день ($1 \le M(i) \le 100{,}000$). Они слишком близки: если $i$ работает, обе соседние в этот день работать не могут (у крайних один сосед). Каждый день можно выбирать другое подмножество.

Нужен максимальный объём за $D$ дней ($1 \le D \le 50,000$). В начале дня есть время обслужить одну выбранную $i$, изменяя её дневной выход $M(i)$ с этого дня и далее. По ежедневным изменениям найдите максимум за $D$ дней (он может не помещаться в 32-битное целое).

Входные данные

• Строка 1: $N$ и $D$.
• Строки $2..1+N$: строка $i+1$ содержит начальное $M(i)$.
• Строки $2+N..1+N+D$: строка $1+N+d$ содержит целые $i$, $m$, заменяющие $M(i)$ на $m$ в начале дня $d$.

Выходные данные

• Строка 1: максимальный общий объём FJ за $D$ дней.

Примеры

Входные данные 1

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

Выходные данные 1

32

Примечание

5 машин с начальными выходами 1,2,3,4,5. В день 1 машина 5 изменяется на 2 единицы, и так далее.

В день 1 оптимум $2+4 = 6$ (также $1+3+2$), в день 2 — $7+4 = 11$, в день 3 — $10+3+2=15$.

Автор задачи: Brian Dean