最佳表现

题目描述

我们有一个长度为 $N$ 的序列 $A=(A_1,A_2,\dots,A_N)$。初始时,所有项都是 $0$。

使用输入中给出的整数 $K$,定义函数 $f(A)$ 如下:

设 $B$ 为将 $A$ 降序排序后得到的序列(即单调不增的序列)。

令 $f(A)=B_1 + B_2 + \dots + B_K$。

我们考虑对该序列进行 $Q$ 次更新。

对 $i=1,2,\dots,Q$,按顺序对序列 $A$ 执行下面的操作,并在每次更新后输出该时刻的 $f(A)$ 的值。

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

输入格式

输入按以下格式从标准输入给出。

$N$ $K$ $Q$
$X_1$ $Y_1$
$X_2$ $Y_2$
$\vdots$
$X_Q$ $Y_Q$

输出格式

共输出 $Q$ 行。第 $i$ 行在第 $i$ 次更新结束时,以整数形式输出 $f(A)$ 的值。

样例

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

在该输入中,$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$。

数据范围

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