P11359 [eJOI 2023] Team Building

你需要集结一个 $N$ 人小队，第 $i$ 个人的能力值为 $s_i$，你可以逐一将每个人加入你的小队。 在你的小队中，每个人拥有两个额外的属性：星语和可爱。加入一个人的过程分三步： - 这个人进入小队，其星语和可爱值均为 $0$。 - 剩余所有人的星语值加上自己的可爱值。 - 剩余所有人的可爱值加上新加入的人的能力值。 最后，你的小队的总星语值定义为所有人的星语值之和，你需要最大化总星语值。 例如，如果你按顺序加入了能力值为 $0,2,2,3$ 的人，所有人的属性变化如下： |行动|星语|可爱| |:-:|:-:|:-:| |加入第一个人|$0$|$0$| |加入第二个人|$0,0$|$0,0$| |更新星语值|$0,0$|$0,0$| |更新可爱值|$0,0$|$\textbf{2},0$| |加入第三个人|$0,0,0$|$2,0,0$| |更新星语值|$\textbf{2},\textbf{0},0$|$2,0,0$| |更新可爱值|$2,0,0$|$\textbf{4},\textbf{2},0$| |加入第四个人|$2,0,0,0$|$4,2,0,0$| |更新星语值|$\textbf{6},\textbf{2},\textbf{0},0$|$4,2,0,0$| |更新可爱值|$6,2,0,0$|$\textbf{7},\textbf{5},\textbf{3},0$| 此时总星语值为 $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$ 行，每行一个整数，代表初始序列和每次修改后的答案。

**【样例解释】** 原始序列的最优方案在题面中已经给出。 第一次修改后的序列为 $(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$。