{"raw_statement":[{"iden":"problem statement","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."},{"iden":"constraints","content":"*   $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."},{"iden":"input","content":"The 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$"},{"iden":"sample input 1","content":"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"},{"iden":"sample output 1","content":"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."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}