Задача №113250. Ограбления
В стране Олимпия очень развита банковская система, поэтому жители охотно кладут свои сбережения в банк. Всего есть 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 -й операций.
- 1 ≤ n ≤ 8, 1 ≤ m ≤ 8 .( 10 баллов)
- 1 ≤ n ≤ 1000, 1 ≤ m ≤ 1000 .( 20 баллов)
- 1 ≤ n ≤ 100 000, 1 ≤ m ≤ 100 000 .( 70 баллов)
7 4 6 7 5 6 2 2 4 6 5 7 2 7 6 4 6
17 18 18 19 19