你想要组建一个包含 $N$ 名程序员的团队。你已经考察了他们，并评估出第 $i$ 个人的技能水平为非负整数 $s[i]$ ($1 \le i \le N$)。你意识到，真正重要的是你雇佣他们的顺序。

每位程序员有两个额外的整数属性：工作率（workrate）和动力（motivation）。他们刚加入时这两个值均为 0，但在雇佣新团队成员后可以增加。当雇佣一名新程序员时，会按以下顺序发生一系列事件：

• 新程序员加入团队，其工作率和动力初始化为 0。
• 其他每位之前已雇佣的程序员的工作率增加其自身的动力值。
• 其他每位之前已雇佣的程序员的动力增加新雇佣者的技能水平。

团队的实力由所有团队成员的工作率之和决定。你的目标是通过优化雇佣顺序来计算出团队能达到的最大实力。

例如，如果你按技能水平 $(0, 2, 2, 3)$ 的顺序雇佣程序员，雇佣过程对他们数值的影响如下：

团队实力计算为 $6 + 2 + 0 + 0 = 8$。然而，如果你以更好的顺序 $(2, 2, 3, 0)$ 雇佣，你将获得 $7 + 3 + 0 + 0 = 10$ 的团队实力。

此外，在接下来的 $Q$ 天里，你会收到关于某些程序员技能水平评估变更的通知。在第 $i$ 天之后，程序员 $x[i]$ 的技能水平将更新为 $y[i]$（可能与之前的值相同）。此更新后的技能值将用于后续天数，直到它再次被更新。

从今天开始，在每一天之后，你的目标是考虑到当时评估的技能水平，通过雇佣所有 $N$ 名程序员来确定最大可达到的团队实力。

输入格式

第一行包含两个整数 $N$ 和 $Q$。 第二行包含整数 $s[1], s[2], \dots, s[N]$。 随后有 $Q$ 行，第 $i$ 行包含两个整数 $x[i]$ 和 $y[i]$。

输出格式

打印 $Q + 1$ 行，每行包含一个整数。这些整数按时间顺序表示每一天之后的最大潜在团队实力。

样例

输入 1

4 2
2 0 2 3
2 4
4 0

输出 1

10
14
12

说明

初始状态的解如上所示。第一天之后，技能水平更新为 $(2, 4, 2, 3)$，最大可达到的团队实力变为 14；第二天之后，技能水平进一步调整为 $(2, 4, 2, 0)$。

数据范围

• $2 \le N \le 50\,000$
• $1 \le Q \le 100\,000$
• $0 \le s[i] \le 100\,000$，对于每个 $1 \le i \le N$
• $1 \le x[i] \le N$，对于每个 $1 \le i \le Q$
• $0 \le y[i] \le 100\,000$，对于每个 $1 \le i \le Q$

子任务

1. (11 分) $N \le 7; Q \le 100$
2. (19 分) $N, Q \le 500$
3. (15 分) $Q \le 10$
4. (6 分) 技能水平从不超过 1
5. (9 分) 技能水平从不超过 500
6. (12 分) $x[i] = 1$，对于每个 $1 \le i \le Q$
7. (10 分) 每次更新会将技能水平改变最多 1
8. (18 分) 无附加限制