Пограбування

В країні Олімпії дуже розвинена банківська система, тому жителі залюбки кладуть свої заощадження в банк. Усього є N банків, які стоять в ряд. У банку номер i зберігається ai тугриків. Початково в банках немає системи безпеки, котра могла б завадити пограбуванню. Однак відомо, що якщо ввечері дня номер $d$ пограбували банк номер $b$, то на ранок наступного дня необхідну систему безпеки буде встановлено у сусідніх банках ($b-1$ та $b+1$), після чого їх вже неможливо буде пограбувати. На ранок дня номер $d+i$ ($i>0$) систему безпеки буде встановлено у банках $b-i$ та $b+i$. Це буде продовжуватись, поки всі банки не буде захищено від пограбування. Пограбований банк вже ніколи не можна пограбувати.

На жаль, в Олімпії навіть злочинці займаються розв’язуванням олімпіадних задач, тому уряд не сумнівається в тому, що якщо хтось замислить провести серію пограбувань, то він зробить це оптимальним чином, інакше кажучи — максимізує сумарну кількість тугриків у тих банках, які йому вдасться пограбувати до того, як в них буде встановлено систему безпеки. Крім того, відомо, що злочинці грабують не більше ніж один банк за день, а також те, що вони орудують лише ввечері.

Банківська система, аналізуючи можливі збитки від пограбувань, розглядає послідовно $M+1$ варіант розміщення коштів у банках. Кожен варіант відрізняється від попереднього кількістю грошей в одному із банків.

Завдання

Напишіть програму robbery, що для кожного з варіантів розміщення коштів у банках підрахує максимальні можливі втрати від пограбувань.

Input

У першому рядку вхідного файла містяться числа $N$ і $M$ — кількість банків та операцій зміни кількості тугриків.

У наступному рядку записано $N$ чисел $a_i$, що задають початкову кількість тугриків у банках.

Далі йдуть $M$ рядків, у кожному з яких записано пару чисел $B$ та $T$, що означає, що після чергової операції в банку номер $B$ стане $T$ тугриків.

Output

У вихідний файл для кожного $i$ ($0\le i\le M$) в окремий рядок виведіть максимальну кількість тугриків, яку зможуть вкрасти злочинці після виконання $i$ операцій.

Examples

Note

У схемі, поданій далі, 0 позначає пограбований банк, а -1 — банк, в якому вже встановили систему безпеки. Початковому варіанту розміщення відповідатимуть такі дії грабіжників:

• $[6,7,5,6,2,2,4]$ — початковий стан;

• $[6,7,5,0,2,2,4]$ — пограбували четвертий банк (6 тугриків);

• $[6,7,-1,0,-1,2,4]$ — ранком наступного дня встановили систему безпеки в сусідні банки;

• $[6,0,-1,0,-1,2,4]$ — пограбували другий банк (7 тугриків);

• $[-1,0,-1,0,-1,-1,4]$ — систему безпеки встановлено в перший банк (через пограбування другого) та в шостий (через пограбування четвертого 2 дні тому);

• $[-1,0,-1,0,-1,-1,0]$ — грабують останній банк (4 тугрики).

В сумі грабіжники мають $17$ тугриків.

Останній варіант розміщення буде таким: $[6,7,5,6,2,5,6]$. Всього грабіжники можуть отримати $6+7+6=19$ тугриків, якщо будуть грабувати четвертий, другий, а потім сьомий банки.

Scoring

Набір тестів складається з 3 блоків, для яких додатково виконуються такі умови:

1. ($10$ балів): $1\le N,M\le 8$;

2. ($20$ балів): $1\le N,M\le 1000$;

3. ($70$ балів): $1\le N,M\le 10^5$.