配点 : $600$ 点

問題文

高橋君は $N$ 種類のカードを $10^{100}$ 枚ずつ持っています。はじめ、$i$ 種類目のカードの得点は $a_i$ で、使用可能枚数は $b_i$ です。

以下の形式のクエリが $Q$ 個与えられるので、順に処理してください。

• 1 x y : $x$ 種類目のカードの得点を $y$ に設定
• 2 x y : $x$ 種類目のカードの使用可能枚数を $y$ に設定
• 3 x : 次の条件を満たすように $x$ 枚のカードを選ぶことができるならば選ばれたカードの得点の総和の最大値を、そうでなければ -1 を出力- どの種類のカードもその使用可能枚数を超えて選ばれない
• どの種類のカードもその使用可能枚数を超えて選ばれない

制約

• $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$ 個以上含まれる
• 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。ただし、$\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$ 種類目のクエリに対する出力をせよ。

3
1 1
2 2
3 3
7
3 4
1 1 10
3 4
2 1 0
2 3 0
3 4
3 2

11
19
-1
4

$1$ 番目の $3$ 種類目のクエリでは、$2$ 種類目のカードを $1$ 枚、$3$ 種類目のカードを $3$ 枚選ぶことで得点の総和が $11$ となり、これが最大です。 $2$ 番目の $3$ 種類目のクエリでは、$1$ 種類目のカードを $1$ 枚、$3$ 種類目のカードを $3$ 枚選ぶことで得点の総和が $19$ となり、これが最大です。 $3$ 番目の $3$ 種類目のクエリでは、$4$ 枚のカードを選ぶことができないため出力は -1 となります。 $4$ 番目の $3$ 種類目のクエリでは、$2$ 種類目のカードを $2$ 枚選ぶことで得点の総和が $4$ となり、これが最大です。