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

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

Завдання

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

Вхідні дані

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

Вихідні дані

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

Оцінювання

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

1. 10 % балів: 1 ≤ N, M ≤ 8.

2. 20 % балів: 1 ≤ N, M ≤ 1000.

3. 70 % балів: 1 ≤ N, M ≤ 100 000.

Пояснення. У схемі, поданій далі, 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 тугриків, якщо будуть грабувати четвертий, другий, а потім сьомий банки.