Ограбление

В стране Олимпии банковская система настолько развита, что жители охотно доверяют свои сбережения банкам. Всего в стране есть 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 блоков, для которых дополнительно выполняются следующие условия:

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 тугриков, если ограбят четвертый, второй, а затем седьмой банки.