AT_abc287_g [ABC287G] Balance Update Query

[problemUrl]: https://atcoder.jp/contests/abc287/tasks/abc287_g 高橋君は $ N $ 種類のカードを $ 10^{100} $ 枚ずつ持っています。はじめ、$ i $ 種類目のカードの得点は $ a_i $ で、使用可能枚数は $ b_i $ です。 以下の形式のクエリが $ Q $ 個与えられるので、順に処理してください。 - `1 x y` : $ x $ 種類目のカードの得点を $ y $ に設定 - `2 x y` : $ x $ 種類目のカードの使用可能枚数を $ y $ に設定 - `3 x` : 次の条件を満たすように $ x $ 枚のカードを選ぶことができるならば選ばれたカードの得点の総和の最大値を、そうでなければ `-1` を出力 - どの種類のカードもその使用可能枚数を超えて選ばれない

入力は以下の形式で標準入力から与えられる。ただし、$ \mathrm{query}_i $ で $ i $ 番目のクエリを表す。 > $ N $ $ a_1 $ $ b_1 $ $ \vdots $ $ a_N $ $ b_N $ $ Q $ $ \mathrm{query}_1 $ $ \vdots $ $ \mathrm{query}_Q $

$ 3 $ 種類目のクエリの個数を $ M $ とする。$ M $ 行出力をせよ。 $ i $ 行目には $ i $ 番目の $ 3 $ 種類目のクエリに対する出力をせよ。

### 制約 - $ 1\ \leq\ N,Q\ \leq\ 2\ \times\ 10^5 $ - $ 0\ \leq\ a_i\ \leq\ 10^9 $ - $ 0\ \leq\ b_i\ \leq\ 10^4 $ - $ 1 $ 種類目のクエリにおいて $ 1\ \leq\ x\ \leq\ N,\ 0\ \leq\ y\ \leq\ 10^9 $ - $ 2 $ 種類目のクエリにおいて $ 1\ \leq\ x\ \leq\ N,\ 0\ \leq\ y\ \leq\ 10^4 $ - $ 3 $ 種類目のクエリにおいて $ 1\ \leq\ x\ \leq\ 10^9 $ - $ 3 $ 種類目のクエリが $ 1 $ 個以上含まれる - 入力はすべて整数 ### Sample Explanation 1 $ 1 $ 番目の $ 3 $ 種類目のクエリでは、$ 2 $ 種類目のカードを $ 1 $ 枚、$ 3 $ 種類目のカードを $ 3 $ 枚選ぶことで得点の総和が $ 11 $ となり、これが最大です。 $ 2 $ 番目の $ 3 $ 種類目のクエリでは、$ 1 $ 種類目のカードを $ 1 $ 枚、$ 3 $ 種類目のカードを $ 3 $ 枚選ぶことで得点の総和が $ 19 $ となり、これが最大です。 $ 3 $ 番目の $ 3 $ 種類目のクエリでは、$ 4 $ 枚のカードを選ぶことができないため出力は `-1` となります。 $ 4 $ 番目の $ 3 $ 種類目のクエリでは、$ 2 $ 種類目のカードを $ 2 $ 枚選ぶことで得点の総和が $ 4 $ となり、これが最大です。