分数: 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,这是最大值。