当前没有测试数据。

E-最佳表现

得分：475分

问题描述

我们有一个长度为N的序列A =（A_1，A_2，...，A_N）。最初，所有的元素都是0。 使用输入中给定的整数K，我们定义一个函数f（A）如下: 将A从大到小排序（使其成为单调非递增序列）, 然后定义$f(A)=B_1 + B_2 + \dots + B_K$。

考虑在这个序列上应用Q个更新。 按照以下顺序对序列A应用以下操作，并在每次更新后打印f(A)的值。

• 将A_Xi的值更改为Y_i。

约束条件

• 所有输入值都是整数。
• $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$

输入

输入格式如下：

N K Q

X_1 Y_1

X_2 Y_2

...

X_Q Y_Q

输出

总共打印Q行。第i行应该包含第i个更新结束时的f(A)的整数值。

示例

输入1

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

输出1

5
6
8
8
15
13
13
11
1
0

在这个例子中，N = 4，K = 2，应用了10次更新。

• 第一次更新将A=(5,0,0,0)，此时f(A)=5。
• 第二次更新将A=(5,1,0,0)，此时f(A)=6。
• 第三次更新将A=(5,1,3,0)，此时f(A)=8。
• 第四次更新将A=(5,1,3,2)，此时f(A)=8。
• 第五次更新将A=(5,10,3,2)，此时f(A)=15。
• 第六次更新将A=(0,10,3,2)，此时f(A)=13。
• 第七次更新将A=(0,10,3,0)，此时f(A)=13。
• 第八次更新将A=(0,10,1,0)，此时f(A)=11。
• 第九次更新将A=(0,0,1,0)，此时f(A)=1。
• 第十次更新将A=(0,0,0,0)，此时f(A)=0。