Пограбування
В країні Олімпії дуже розвинена банківська система, тому жителі залюбки кладуть свої заощадження в банк. Усього є N банків, які стоять в ряд. У банку номер i зберігається a[i] тугриків. Початково в банках немає системи безпеки, котра могла б завадити пограбуванню. Однак відомо, що якщо ввечері дня номер d пограбували банк номер b, то на ранок наступного дня необхідну систему безпеки буде встановлено у сусідніх банках (b − 1 та b + 1), після чого їх вже неможливо буде пограбувати. На ранок дня номер d + i (i > 0) систему безпеки буде встановлено у банках b − i та b + i. Це буде продовжуватись, поки всі банки не буде захищено від пограбування. Пограбований банк вже ніколи не можна пограбувати.На жаль, в Олімпії навіть злочинці займаються розв’язуванням олімпіадних задач, тому уряд не сумнівається в тому, що якщо хтось замислить провести серію пограбувань, то він зробить це оптимальним чином, інакше кажучи — максимізує сумарну кількість тугриків у тих банках, які йому вдасться пограбувати до того, як в них буде встановлено систему безпеки. Крім того, відомо, що злочинці грабують не більше ніж один банк за день, а також те, що вони орудують лише ввечері.
Банківська система, аналізуючи можливі збитки від пограбувань, розглядає послідовно M+1 варіант розміщення коштів у банках. Кожен варіант відрізняється від попереднього кількістю грошей в одному із банків.
####Завдання
Напишіть програму, що для кожного з варіантів розміщення коштів у банках підрахує максимальні можливі втрати від пограбувань.
Вхідні дані
У першому рядку вхідних даних містяться числа N і M — кількість банків та операцій зміни кількості тугриків. У наступному рядку записано N чисел a[i], що задають початкову кількість тугриків у банках. Далі йдуть M рядків, у кожному з яких записано пару чисел B та T, що означає, що після чергової операції в банку номер B стане T тугриків.
Вихідні дані
У вихідні дані для кожного i (0 ≤ i ≤ M) в окремий рядок виведіть максимальну кількість тугриків, яку зможуть вкрасти злочинці після виконання i операцій.
####Оцінювання
Набір тестів складається з 3 блоків, для яких додатково виконуються такі умови:
10 % балів:
1 ≤ N, M ≤ 8.20 % балів:
1 ≤ N, M ≤ 1000.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 тугриків, якщо будуть грабувати четвертий, другий, а потім сьомий банки.