题目描述

高橋君は $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$ 種類目のクエリに対する出力をせよ。

题目大意

有 $n$ 种卡片, 每种卡片有两种属性: 价值$A_i$ 和数目 $B_i$, 要求支持 $3$ 种操作

• 读入$(1, x, y)$, 将$A_x$ 的数值改为 $y$。
• 读入$(2, x, y)$, 将$B_x$ 的数值改为 $y$。
• 读入$(3, x)$, 输出在所有卡片中选择$x$张卡片的最大价值, 若$\sum\limits_{i=1}^{n}B_i <x$, 则输出$-1$

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\ \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$ となり、これが最大です。