{"raw_statement":[{"iden":"problem statement","content":"We have a sequence $A=(A_1,A_2,\\dots,A_N)$ of length $N$. Initially, all the terms are $0$.  \nUsing an integer $K$ given in the input, we define a function $f(A)$ as follows:\n\n*   Let $B$ be the sequence obtained by sorting $A$ in descending order (so that it becomes monotonically non-increasing).\n*   Then, let $f(A)=B_1 + B_2 + \\dots + B_K$.\n\nWe consider applying $Q$ updates on this sequence.  \nApply the following operation on the sequence $A$ for $i=1,2,\\dots,Q$ in this order, and print the value $f(A)$ at that point after each update.\n\n*   Change $A_{X_i}$ to $Y_i$."},{"iden":"constraints","content":"*   All input values are integers.\n*   $1 \\le K \\le N \\le 5 \\times 10^5$\n*   $1 \\le Q \\le 5 \\times 10^5$\n*   $1 \\le X_i \\le N$\n*   $0 \\le Y_i \\le 10^9$"},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $K$ $Q$\n$X_1$ $Y_1$\n$X_2$ $Y_2$\n$\\vdots$\n$X_Q$ $Y_Q$"},{"iden":"sample input 1","content":"4 2 10\n1 5\n2 1\n3 3\n4 2\n2 10\n1 0\n4 0\n3 1\n2 0\n3 0"},{"iden":"sample output 1","content":"5\n6\n8\n8\n15\n13\n13\n11\n1\n0\n\nIn this input, $N=4$ and $K=2$. $Q=10$ updates are applied.\n\n*   The $1$\\-st update makes $A=(5, 0,0,0)$. Now, $f(A)=5$.\n*   The $2$\\-nd update makes $A=(5, 1,0,0)$. Now, $f(A)=6$.\n*   The $3$\\-rd update makes $A=(5, 1,3,0)$. Now, $f(A)=8$.\n*   The $4$\\-th update makes $A=(5, 1,3,2)$. Now, $f(A)=8$.\n*   The $5$\\-th update makes $A=(5,10,3,2)$. Now, $f(A)=15$.\n*   The $6$\\-th update makes $A=(0,10,3,2)$. Now, $f(A)=13$.\n*   The $7$\\-th update makes $A=(0,10,3,0)$. Now, $f(A)=13$.\n*   The $8$\\-th update makes $A=(0,10,1,0)$. Now, $f(A)=11$.\n*   The $9$\\-th update makes $A=(0, 0,1,0)$. Now, $f(A)=1$.\n*   The $10$\\-th update makes $A=(0, 0,0,0)$. Now, $f(A)=0$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}