← 返回题目列表

AtCoder · abc287_g

G. 余额更新查询

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

高桥有 10^{100} 每张卡片 N 种。 最初,分数和名额 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-st 种, 1 \leq x \leq N 和 0 \leq y \leq 10^9.
  • 对于每个查询 2-第一种, 1 \leq x \leq N 和 0 \leq y \leq 10^4.
  • 对于每个查询 3-rd 种, 1 \leq x \leq 10^9.
  • 至少有一个查询 3-rd 种。
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出,其中 \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-rd 种。
的 i-th 行应包含对 i-第一个这样的查询。


示例输入 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

示例输出 1

11
19
-1
4

对于第一个查询 3-rd 种,你可以选择一张牌 2-nd 种和三张牌 3-rd 类,总分为 11,这是最大值。
对于第二个此类查询,您可以选择以下一张卡 1-st 种类和三张牌 3-rd 类,总分为 19,这是最大值。
对于第三个此类查询,您不能选择四张牌,因此 应打印 -1 。
对于第四个此类查询,您可以选择以下两张牌 2-nd 类,总分为 4,这是最大值。