题目描述

你需要集结一个 $N$ 人小队，第 $i$ 个人的能力值为 $s_i$，你可以逐一将每个人加入你的小队。

在你的小队中，每个人拥有两个额外的属性：星语和可爱。加入一个人的过程分三步：

• 这个人进入小队，其星语和可爱值均为 $0$。
• 剩余所有人的星语值加上自己的可爱值。
• 剩余所有人的可爱值加上新加入的人的能力值。

最后，你的小队的总星语值定义为所有人的星语值之和，你需要最大化总星语值。

例如，如果你按顺序加入了能力值为 $0,2,2,3$ 的人，所有人的属性变化如下：

此时总星语值为 $6+2+0+0=8$，但是将顺序改为 $2,2,3,0$ 就可以得到 $7+3+0+0=10$。

你还需要处理 $Q$ 次修改，每次修改会将第 $x_i$ 个人的能力值改为 $y_i$，你需要求出每次修改后的最大总星语值，修改之间不独立，即每次修改在下一次保留。

输入格式

第一行输入两个整数 $N,Q$。

第二行输入 $N$ 个整数 $s_i$。

接下来 $Q$ 行，每行输入两个整数 $x_i,y_i$。

输出格式

输出 $Q+1$ 行，每行一个整数，代表初始序列和每次修改后的答案。

4 2
2 0 2 3
2 4
4 0

10
14
12

提示

【样例解释】

原始序列的最优方案在题面中已经给出。

第一次修改后的序列为 $(2,4,2,3)$。

第二次修改后的序列为 $(2,4,2,0)$。

【数据范围】

本题采用捆绑测试。

• Subtask 1（11 pts）：$N\leq 7$，$Q\leq 100$。
• Subtask 2（19 pts）：$N,Q\leq 500$。
• Subtask 3（15 pts）：$Q\leq 10$。
• Subtask 4（6 pts）：$s_i,y_i\leq 1$。
• Subtask 5（9 pts）：$s_i,y_i\leq 500$。
• Subtask 6（12 pts）：$x_i=1$。
• Subtask 7（10 pts）：每次修改和原来的数之差不超过 $1$。
• Subtask 8（18 pts）：无特殊限制。

对于 $100\%$ 的数据，保证 $2\leq N\leq 5\times 10^4$，$1\leq Q\leq 10^5$，$0\leq s_i\leq 10^5$，$1\leq x_i\leq N$，$0\leq y_i\leq 10^5$。