题目描述

Olympia 国的银行系统非常发达，因为居民们很喜欢储蓄。该国的货币单位是 tugrik。

全国有 $N$ 家银行，编号为 $1$ 到 $N$。编号为 $i$ 的银行中存有 $a_i$ 个 tugrik。

一开始，没有任何银行安装防抢劫的安保系统。不过该国有一条“明智”的规定：如果在第 $d$ 天晚上，编号为 $b$ 的银行被抢劫，那么在第 $d+1$ 天早上，编号为 $b-1$ 和 $b+1$ 的银行会安装安保系统，如果这些银行存在的话。安装安保系统的过程还会继续：对任意 $i>0$，在第 $d+i$ 天早上，编号为 $b-i$ 和 $b+i$ 的银行会安装安保系统，如果这些银行存在的话。

已经被抢劫过的银行不会再次被抢劫。

现在 Olympia 形成了一个由会解决复杂信息学问题的盗贼组成的团伙。他们计划连续实施一系列抢劫，使得在所有银行都被安保系统保护或已经被抢劫之前，抢到的钱数尽可能多。团伙每天晚上最多实施一次抢劫。

银行系统管理层想分析可能损失。他们要考虑 $M+1$ 种银行存款分布方案，编号为 $1$ 到 $M+1$。第 $1$ 种是初始方案。每个后续方案都只是在前一个方案的基础上，改变恰好一家银行中的钱数。

对每一种方案，损失定义为盗贼在最优行动下能够抢到的最大钱数。

请你编写程序，求出每种方案对应的最大可能损失。

输入格式

第一行包含两个正整数 $N,M$，分别表示银行数量和修改次数。

第二行包含 $N$ 个非负整数 $a_i$，表示初始时第 $i$ 家银行的钱数。

接下来 $M$ 行，每行包含两个整数 $B,T$，表示把编号为 $B$ 的银行中存放的钱数改为 $T$。

输出格式

输出 $M+1$ 行。第 $i$ 行输出一个整数，表示第 $i$ 种银行存款分布方案下，盗贼最优行动能够抢到的最大钱数。

数据范围

• $1 \le N \le 10^5$；
• $1 \le M \le 10^5$；
• $0 \le a_i \le 10^5$。

部分测试限制：

• $10\%$ 的测试中，$1\le N\le 8$，$1\le M\le 8$；
• $50\%$ 的测试中，$1\le N\le 1000$，$1\le M\le 1000$。

每个测试点单独计分。

样例

输入

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 tugrik
6 7 -1 0 -1 2 4    次日早晨，3 号和 5 号银行安装安保系统
6 0 -1 0 -1 2 4    抢劫了 2 号银行，得到 7 tugrik
-1 0 -1 0 -1 -1 4  1 号和 6 号银行安装安保系统
-1 0 -1 0 -1 -1 0  抢劫了 7 号银行，得到 4 tugrik

此时不再存在既未被抢劫又未被保护的银行，所以团伙一共抢到 $17$ 个 tugrik。

最后一种方案为

6 7 5 6 2 5 6

此时最大收益为 $6+7+6$，可以通过抢劫第 $4$、第 $2$、第 $7$ 家银行获得。