F - Egoism 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 550 点

問題文

AtCoder 牧場では馬がみずから水浴びをします。後片づけをする馬もいれば、散らかしたままにする馬もいます。

N 頭の馬がおり、1 から N までの番号が付けられています。馬 i (1 \leq i \leq N) は機嫌 A_i と丁寧さ B_i をもちます(ここで、B_i は 1, 2 のいずれか)。

夜になると、N 頭の馬が 1 回ずつ水浴びをします。j 回目 (1 \leq j \leq N) に水浴びをする馬の番号を p_j とおくと、馬 p_j の満足度が以下で与えられます。

  • j \geq 2 の場合、馬 p_j の機嫌と馬 p_{j-1} の丁寧さの積。
  • j = 1 の場合、馬 p_j の機嫌。

これから Q 日にわたって毎日 1 つずつクエリが与えられるので、順に処理してください。k 日目 (1 \leq k \leq Q) のクエリは以下の通りです。

  • 馬 W_k の機嫌を X_k に、丁寧さを Y_k に変更する(ここで、Y_k は 1, 2 のいずれか)。その後、その夜に N 頭の馬が水浴びをする順番を任意に決められるとき、その夜の N 頭の水浴びの満足度の総和が最大でいくらになるかを求める。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^6 (1 \leq i \leq N)
  • B_i は 1,2 のいずれか (1 \leq i \leq N)
  • 1 \leq W_k \leq N (1 \leq k \leq Q)
  • 1 \leq X_k \leq 10^6 (1 \leq k \leq Q)
  • Y_k は 1,2 のいずれか (1 \leq k \leq Q)
  • 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N Q
A_1 B_1
\vdots
A_N B_N
W_1 X_1 Y_1
\vdots
W_Q X_Q Y_Q

出力

Q 行出力せよ。k 行目 (1 \leq k \leq Q) には k 日目のクエリの答えを出力せよ。

入力例 1

4 4
1 2
10 1
3 1
7 2
2 7 1
1 3 1
2 2 1
3 1000000 2

出力例 1

32
27
18
2000015

1 日目のクエリにおいて、馬 3,1,4,2 の順に水浴びすることで、各馬の満足度は以下のようになります。

  • 馬 3 の満足度は 3
  • 馬 1 の満足度は 1 \times 1 = 1
  • 馬 4 の満足度は 7 \times 2 = 14
  • 馬 2 の満足度は 7 \times 2 = 14

このときの満足度の総和は 32 です。

2 日目のクエリにおいて、馬 4,2,1,3 の順に水浴びすることで、各馬の満足度は以下のようになります。

  • 馬 4 の満足度は 7
  • 馬 2 の満足度は 7 \times 2 = 14
  • 馬 1 の満足度は 3 \times 1 = 3
  • 馬 3 の満足度は 3 \times 1 = 3

このときの満足度の総和は 27 です。

3 日目のクエリにおいて、馬 4,3,2,1 の順に水浴びすることで、満足度の総和は 18 になります。

4 日目のクエリにおいて、馬 4,3,1,2 の順に水浴びすることで、満足度の総和は 2000015 になります。

入力例 2

10 10
340019 2
598908 1
177330 2
575439 2
916653 2
451275 2
762769 2
36625 2
273231 2
367619 2
8 334230 2
8 835378 1
4 777076 2
6 61501 1
4 516395 1
4 35678 2
5 751493 1
3 815798 1
2 369777 2
5 941470 2

出力例 2

9417616
10146681
10549955
9708906
8847525
8463663
7860112
8606740
8516097
9236070

Score : 550 points

Problem Statement

At AtCoder Ranch, horses bathe themselves. Some horses clean up afterward, while others leave a mess.

There are N horses, numbered 1 to N. Horse i (1 \leq i \leq N) has a mood A_i and a tidiness B_i (where B_i is 1 or 2).

At night, the N horses bathe once each. Let p_j be the number of the horse that bathes in the j-th turn (1 \leq j \leq N). The satisfaction of horse p_j is given as follows:

  • If j \geq 2, the product of the mood of horse p_j and the tidiness of horse p_{j-1}.
  • If j = 1, the mood of horse p_j.

You will be given Q queries, one for each day over Q days. Process them in order. The query for the k-th day (1 \leq k \leq Q) is as follows:

  • Change the mood of horse W_k to X_k and its tidiness to Y_k (where Y_k is 1 or 2). Then, find the maximum possible total satisfaction of the N horses' baths that night if you can decide the order in which the N horses bathe arbitrarily.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^6 (1 \leq i \leq N)
  • B_i is 1 or 2. (1 \leq i \leq N)
  • 1 \leq W_k \leq N (1 \leq k \leq Q)
  • 1 \leq X_k \leq 10^6 (1 \leq k \leq Q)
  • Y_k is 1 or 2. (1 \leq k \leq Q)
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N Q
A_1 B_1
\vdots
A_N B_N
W_1 X_1 Y_1
\vdots
W_Q X_Q Y_Q

Output

Output Q lines. The k-th line (1 \leq k \leq Q) should contain the answer to the query for the k-th day.

Sample Input 1

4 4
1 2
10 1
3 1
7 2
2 7 1
1 3 1
2 2 1
3 1000000 2

Sample Output 1

32
27
18
2000015

For the query on the first day, if the horses bathe in the order 3,1,4,2, the satisfaction of each horse is as follows:

  • Horse 3's satisfaction is 3
  • Horse 1's satisfaction is 1 \times 1 = 1
  • Horse 4's satisfaction is 7 \times 2 = 14
  • Horse 2's satisfaction is 7 \times 2 = 14

The total satisfaction in this case is 32.

For the query on the second day, if the horses bathe in the order 4,2,1,3, the satisfaction of each horse is as follows:

  • Horse 4's satisfaction is 7
  • Horse 2's satisfaction is 7 \times 2 = 14
  • Horse 1's satisfaction is 3 \times 1 = 3
  • Horse 3's satisfaction is 3 \times 1 = 3

The total satisfaction in this case is 27.

For the query on the third day, if the horses bathe in the order 4,3,2,1, the total satisfaction is 18.

For the query on the fourth day, if the horses bathe in the order 4,3,1,2, the total satisfaction is 2000015.

Sample Input 2

10 10
340019 2
598908 1
177330 2
575439 2
916653 2
451275 2
762769 2
36625 2
273231 2
367619 2
8 334230 2
8 835378 1
4 777076 2
6 61501 1
4 516395 1
4 35678 2
5 751493 1
3 815798 1
2 369777 2
5 941470 2

Sample Output 2

9417616
10146681
10549955
9708906
8847525
8463663
7860112
8606740
8516097
9236070