题目描述

本题译自 eJOI2023 Problem F. Team Building

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

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

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

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

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

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

此外，在接下来的 $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$）

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