当前没有测试数据。

题目描述

给定长度为 $N$ 的数列 $A=(A_1,A_2,\dots,A_N)$，最开始所有项均为 $0$。

定义函数 $f(A)$ 如下：

将 $A$ 按照降序排序得到 $B$。

则 $f(A)=B_1+B_2+\dots+B_K$，其中 $B$ 为排序后的数列，$K$ 为 $A$ 中不为 $0$ 的元素个数。

现在对该数列进行 $Q$ 次更新。对于每次更新，按顺序执行以下操作，并输出此时的 $f(A)$ 值：

将 $A_{X_i}$ 更改为 $Y_i$。

输入格式

第一行输入 $N$ $K$ $Q$

接下来 $Q$ 行每行输入两个数字分别为 $X_i$ $Y_i$

输出格式

输出一共输出 $Q$ 行，简单来说即输出 前 $K$ 大元素之和，若不足 $K$ 个，则输出所有数字的和。

4 2 10
1 5
2 1
3 3
4 2
2 10
1 0
4 0
3 1
2 0
3 0

5
6
8
8
15
13
13
11
1
0

提示

数据范围

• $1\ \le\ K\ \le\ N\ \le\ 5\ \times\ 10^5$
• $1\ \le\ Q\ \le\ 5\ \times\ 10^5$
• $1\ \le\ X_i\ \le\ N$
• $0\ \le\ Y_i\ \le\ 10^9$

Sample Explanation 1

在这个输入中，$N=4$ 和 $K=2$。共应用了 $Q=10$ 次更新。

• 第 1 次更新后，$A=(5, 0, 0, 0)$。此时，$f(A)=5$。
• 第 2 次更新后，$A=(5, 1, 0, 0)$。此时，$f(A)=6$。
• 第 3 次更新后，$A=(5, 1, 3, 0)$。此时，$f(A)=8$。
• 第 4 次更新后，$A=(5, 1, 3, 2)$。此时，$f(A)=8$。
• 第 5 次更新后，$A=(5, 10, 3, 2)$。此时，$f(A)=15$。
• 第 6 次更新后，$A=(0, 10, 3, 2)$。此时，$f(A)=13$。
• 第 7 次更新后，$A=(0, 10, 3, 0)$。此时，$f(A)=13$。
• 第 8 次更新后，$A=(0, 10, 1, 0)$。此时，$f(A)=11$。
• 第 9 次更新后，$A=(0, 0, 1, 0)$。此时，$f(A)=1$。
• 第 10 次更新后，$A=(0, 0, 0, 0)$。此时，$f(A)=0$。