{"problem":{"name":"Best Performances","description":{"content":"We have a sequence $A=(A_1,A_2,\\dots,A_N)$ of length $N$. Initially, all the terms are $0$.   Using an integer $K$ given in the input, we define a function $f(A)$ as follows: *   Let $B$ be the seque","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":6000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc306_e"},"statements":[{"statement_type":"Markdown","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$.\n\n## Constraints\n\n*   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$\n\n## Input\n\nThe 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc306_e","tags":[],"sample_group":[["4 2 10\n1 5\n2 1\n3 3\n4 2\n2 10\n1 0\n4 0\n3 1\n2 0\n3 0","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$."]],"created_at":"2026-03-03 11:01:14"}}