Пограбування#7664
В країні Олімпії дуже розвинена банківська система, тому жителі залюбки кладуть свої заощадження в банк. Усього є банків, які стоять в ряд. У банку номер зберігається a_i тугриків. Початково в банках немає системи безпеки, котра могла б завадити пограбуванню. Однак відомо, що якщо ввечері дня номер пограбували банк номер , то на ранок наступного дня необхідну систему безпеки буде встановлено у сусідніх банках (b - 1 та b + 1), після чого їх вже неможливо буде пограбувати. На ранок дня номер d + i (i > 0) систему безпеки буде встановлено у банках b - i та b + i. Це буде продовжуватись, поки всі банки не буде захищено від пограбування. Пограбований банк вже ніколи не можна пограбувати.
На жаль, в Олімпії навіть злочинці займаються розв'язуванням олімпіадних задач, тому уряд не сумнівається в тому, що якщо хтось замислить провести серію пограбувань, то він зробить це оптимальним чином, інакше кажучи — максимізує сумарну кількість тугриків у тих банках, які йому вдасться пограбувати до того, як в них буде встановлено систему безпеки. Крім того, відомо, що злочинці грабують не більше ніж один банк за день, а також те, що вони орудують лише ввечері.
Банківська система, аналізуючи можливі збитки від пограбувань, розглядає послідовно M + 1 варіант розміщення коштів у банках. Кожен варіант відрізняється від попереднього кількістю грошей в одному із банків.
Напишіть програму, що для кожного з варіантів розміщення коштів у банках підрахує максимальні можливі втрати від пограбувань.
У першому рядку вхідних даних містяться числа і — кількість банків та операцій зміни кількості тугриків. У наступному рядку записано чисел a_i, що задають початкову кількість тугриків у банках. Далі йдуть рядків, у кожному з яких записано пару чисел та , що означає, що після чергової операції в банку номер стане тугриків.
У вихідні дані для кожного (0 \le i \le M) в окремий рядок виведіть максимальну кількість тугриків, яку зможуть вкрасти злочинці після виконання операцій.
Приклад 1
У схемі, поданій далі, позначає пограбований банк, а — банк, в якому вже встановили систему безпеки.
Початковому варіанту розміщення відповідатимуть такі дії грабіжників:
6\ 7\ 5\ 6\ 2\ 2\ 4 — початковий стан;
6\ 7\ 5\ 0\ 2\ 2\ 4 — пограбували четвертий банк ( тугриків);
6\ 7\ {-1}\ 0\ {-1}\ 2\ 4 — ранком наступного дня встановили систему безпеки в сусідні банки;
6\ 0\ {-1}\ 0\ {-1}\ 2\ 4 — пограбували другий банк ( тугриків);
{-1}\ 0\ {-1}\ 0\ {-1}\ {-1}\ 4 — систему безпеки встановлено в перший банк (через пограбування другого) та в шостий (через пограбування четвертого дні тому);
{-1}\ 0\ {-1}\ 0\ {-1}\ {-1}\ 0 — грабують останній банк ( тугрики).
В сумі грабіжники мають тугриків.
Останній варіант розміщення буде таким: 6\ 7\ 5\ 6\ 2\ 5\ 6. Всього грабіжники можуть отримати 6 + 7 + 6 = 19 тугриків, якщо будуть грабувати четвертий, другий, а потім сьомий банки.
Набір тестів складається з блоків, для яких додатково виконуються такі умови:
% балів: 1 \le N, M \le 8.
% балів: 1 \le N, M \le 1000.
% балів: 1 \le N, M \le 100\,000.