题目描述

奥林匹亚国的银行系统非常发达，因此居民们很喜欢把积蓄存入银行。共有 $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\le i\le M$），输出一行，表示执行前 $i$ 次修改后，罪犯最多能够抢到的金额总和。

数据范围与评分

测试点由 3 个子任务组成：

1. 10 分：$1\le N,M\le 8$；
2. 20 分：$1\le N,M\le 1000$；
3. 70 分：$1\le N,M\le 10^5$。

样例

7 4
6 7 5 6 2 2 4
6 5
7 2
7 6
4 6

17
18
18
19
19

样例解释

在下面的示意中，$0$ 表示已经被抢劫的银行，$-1$ 表示已经安装安全系统的银行。

初始配置下，罪犯可以采取如下行动：

• $[6,7,5,6,2,2,4]$：初始状态；
• $[6,7,5,0,2,2,4]$：抢劫第 $4$ 家银行，得到 $6$；
• $[6,7,-1,0,-1,2,4]$：第二天早上，第 $3$ 和第 $5$ 家银行安装安全系统；
• $[6,0,-1,0,-1,2,4]$：抢劫第 $2$ 家银行，得到 $7$；
• $[-1,0,-1,0,-1,-1,4]$：第 $1$ 家银行因第 $2$ 家银行被抢而安装安全系统，第 $6$ 家银行因第 $4$ 家银行两天前被抢而安装安全系统；
• $[-1,0,-1,0,-1,-1,0]$：抢劫最后一家银行，得到 $4$。

总共得到 $17$。

最后一种配置为 $[6,7,5,6,2,5,6]$。罪犯可以抢劫第 $4$、第 $2$、第 $7$ 家银行，总金额为 $6+7+6=19$。