余额更新查询

题目描述

高桥君有 $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$

输出格式

输出 $M$ 行,其中 $M$ 为第 3 种查询的个数。

第 $i$ 行输出第 $i$ 个此类查询的答案。

样例

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 种查询,可以选 1 张第 2 种卡片和 3 张第 3 种卡片,分数之和为 $11$,这是最大值。

对第 2 个此类查询,可以选 1 张第 1 种卡片和 3 张第 3 种卡片,分数之和为 $19$,这是最大值。

对第 3 个此类查询,无法选出 4 张卡片,因此输出 -1。

对第 4 个此类查询,可以选 2 张第 2 种卡片,分数之和为 $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 种查询。
• 输入中的所有值均为整数。