题目描述

本题译自 eJOI2023 Problem F. Team Building

你想要组建一个由 $N$ 名程序员组成的团队。你已经考察了这些程序员，并确定了第 $i$ $(1 \leq i \leq N)$ 个人的技能水平，用非负整数 $s_i$ 表示。你意识到，真正重要的是你雇佣他们的顺序。

每个程序员还有两个额外的整数值特征：工作效率和动力，这两个值在他们刚加入时都是 $0$，但在招聘新团队成员后可以增加。当雇佣一名新程序员时，以下事件将按给定顺序发生：

• 新程序员加入团队，工作效率和动力初始为 $0$。
• 每个之前雇佣的程序员的工作效率将加上他们自己的动力值。
• 每个之前雇佣的程序员的动力将加上新雇员的技能水平。

团队的实力由最后所有团队成员的工作效率之和决定。你的目标是计算出通过优化招聘顺序可实现的最大团队实力。

例如，如果你按照这个顺序 $(0, 2, 2, 3)$ 雇佣技能水平为 $(0, 2, 2, 3)$ 的程序员，他们的值将随着招聘过程的进行而发生如下变化：

事件	工作效率	动力
雇佣技能为 0 的人	0	0
雇佣技能为 2 的人	0 0	0 0
更新工作效率	0 0	0 0
更新动力	0 0	2 0
雇佣技能为 2 的人	0 0 0	2 0 0
更新工作效率	2 0 0	2 0 0
更新动力	2 0 0	4 2 0
雇佣技能为 3 的人	2 0 0 0	4 2 0 0
更新工作效率	6 2 0 0	4 2 0 0
更新动力	6 2 0 0	7 5 3 0

团队实力将为 $6 + 2 + 0 + 0 = 8$。然而，如果你以 $(2, 2, 3, 0)$ 的顺序雇佣程序员，你将实现团队实力为 $7 + 3 + 0 + 0 = 10$。

新雇员技能	工作效率	动力
2	0	0
2	0 0	2 0
3	2 0 0	5 3 0
0	7 3 0 0	5 3 0 0

此外，在接下来的 $Q$ 天里，你将收到关于某些程序员技能水平变化的通知。在第 $i$ 天后，程序员 $x_i$ 的技能水平将被更新为 $y_i$（可能与之前的值相同）。在接下来的日子中程序员 $x_i$ 的技能值就一直为 $y_i$，直到他再次被更新。

你的目标是对于每个 $0\leq i \leq Q$，计算当第 $i$ 天结束时，通过雇佣所有 $N$ 名程序员，在当时评估的技能水平下可实现的最大团队实力。

输入格式

第一行包含两个整数 $N$ 和 $Q$。

第二行包含 $N$ 个整数，表示 $s_1, s_2, \ldots , s_N$。

接下来的 $Q$ 行，第 $i$ 行包含两个整数：$x_i$ 和 $y_i$。

输出格式

输出 $Q + 1$ 行，每行一个整数。表示第 $i$ 天结束后可实现的最大团队实力。

4 2
2 0 2 3
2 4
4 0

10
14
12

初始状态的招聘顺序如题目描述所示。第一天后，技能水平将被更新为 $(2, 4, 2, 3)$，最大可达团队实力变为 $14$，第二天后，技能水平将被进一步调整为 $(2, 4, 2, 0)$。

数据范围与提示

对于所有输入数据，满足：

• $2 \leq N \leq 5\times 10^5$
• $1 \leq Q \leq 10^5$
• $0 \leq s_i \leq 10^5\ (1 \leq i \leq N)$
• $1 \leq x_i \leq N\ (1 \leq i \leq Q)$
• $0 \leq y_i \leq 10^5\ (1 \leq i \leq Q)$

详细子任务附加限制及分值如下表所示。

子任务	附加限制	分值
$1$	$N \leq 7; Q \leq 100$	$11$
$2$	$N , Q \leq 500$	$19$
$3$	$Q \leq 10$	$15$
$4$	技能水平永远不超过 $1$	$6$
$5$	技能水平永远不超过 $500$	$9$
$6$	$x_i = 1\ (1 \leq i \leq Q)$	$12$
$7$	每次技能水平变化不超过 $1$	$10$
$8$	无附加限制	$18$