{"problem":{"name":"Balance Update Query","description":{"content":"Takahashi has $10^{100}$ cards of each of $N$ kinds. Initially, the score and quota of the $i$\\-th kind of card are set to $a_i$ and $b_i$, respectively. Given $Q$ queries in the following formats, pr","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc287_g"},"statements":[{"statement_type":"Markdown","content":"Takahashi has $10^{100}$ cards of each of $N$ kinds. Initially, the score and quota of the $i$\\-th kind of card are set to $a_i$ and $b_i$, respectively.\nGiven $Q$ queries in the following formats, process them in order.\n\n*   `1 x y`: set the score of the $x$\\-th kind of card to $y$.\n*   `2 x y`: set the quota of the $x$\\-th kind of card to $y$.\n*   `3 x`: if one can choose $x$ cards subject to the following condition, print the maximum possible sum of the scores of the chosen cards; print `-1` otherwise.\n    *   The number of chosen cards of each kind does not exceed its quota.\n\n## Constraints\n\n*   $1 \\leq N,Q \\leq 2 \\times 10^5$\n*   $0 \\leq a_i \\leq 10^9$\n*   $0 \\leq b_i \\leq 10^4$\n*   For each query of the $1$\\-st kind, $1 \\leq x \\leq N$ and $0 \\leq y \\leq 10^9$.\n*   For each query of the $2$\\-nd kind, $1 \\leq x \\leq N$ and $0 \\leq y \\leq 10^4$.\n*   For each query of the $3$\\-rd kind, $1 \\leq x \\leq 10^9$.\n*   There is at least one query of the $3$\\-rd kind.\n*   All values in the input are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format, where $\\mathrm{query}_i$ denotes the $i$\\-th query:\n\n$N$\n$a_1$ $b_1$\n$\\vdots$\n$a_N$ $b_N$\n$Q$\n$\\mathrm{query}_1$\n$\\vdots$\n$\\mathrm{query}_Q$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc287_g","tags":[],"sample_group":[["3\n1 1\n2 2\n3 3\n7\n3 4\n1 1 10\n3 4\n2 1 0\n2 3 0\n3 4\n3 2","11\n19\n-1\n4\n\nFor the first query of the $3$\\-rd kind, you can choose one card of the $2$\\-nd kind and three cards of the $3$\\-rd kind for a total score of $11$, which is the maximum.  \nFor the second such query, you can choose one card of the $1$\\-st kind and three cards of the $3$\\-rd kind for a total score of $19$, which is the maximum.  \nFor the third such query, you cannot choose four cards, so `-1` should be printed.  \nFor the fourth such query, you can choose two cards of the $2$\\-nd kind for a total score of $4$, which is the maximum."]],"created_at":"2026-03-03 11:01:14"}}