G - Balance Update Query Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 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 種類目のクエリに対する出力をせよ。

入力例 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

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

Score : 600 points

Problem Statement

Takahashi has 10^{100} cards of each of N kinds. Initially, the score and quota of the i-th kind of card are set to a_i and b_i, respectively.

Given Q queries in the following formats, process them in order.

  • 1 x y: set the score of the x-th kind of card to y.
  • 2 x y: set the quota of the x-th kind of card to y.
  • 3 x: if one can choose x cards subject to the following condition, print the maximum possible sum of the scores of the chosen cards; print -1 otherwise.
    • The number of chosen cards of each kind does not exceed its quota.

Constraints

  • 1 \leq N,Q \leq 2 \times 10^5
  • 0 \leq a_i \leq 10^9
  • 0 \leq b_i \leq 10^4
  • For each query of the 1-st kind, 1 \leq x \leq N and 0 \leq y \leq 10^9.
  • For each query of the 2-nd kind, 1 \leq x \leq N and 0 \leq y \leq 10^4.
  • For each query of the 3-rd kind, 1 \leq x \leq 10^9.
  • There is at least one query of the 3-rd kind.
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format, where \mathrm{query}_i denotes the i-th query:

N
a_1 b_1
\vdots
a_N b_N
Q
\mathrm{query}_1
\vdots
\mathrm{query}_Q

Output

Print M lines, where M is the number of queries of the 3-rd kind.
The i-th line should contain the response to the i-th such query.

Sample Input 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

Sample Output 1

11
19
-1
4

For the first query of the 3-rd kind, you can choose one card of the 2-nd kind and three cards of the 3-rd kind for a total score of 11, which is the maximum.
For the second such query, you can choose one card of the 1-st kind and three cards of the 3-rd kind for a total score of 19, which is the maximum.
For the third such query, you cannot choose four cards, so -1 should be printed.
For the fourth such query, you can choose two cards of the 2-nd kind for a total score of 4, which is the maximum.