I - Email Scheduling Optimization Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 525 点

問題文

長さ N の正整数列 A=(A_1,A_2,\dots,A_N),\;B=(B_1,B_2,\dots,B_N) が与えられます。
Q 個のクエリが与えられます。
各クエリは以下の 2 種類のいずれかです。

  • 1 i x : A_i を x に変更する。
  • 2 i x : B_i を x に変更する。

各クエリを処理するたびに、以下の問題の答えを求めてください。

高橋君は N 個の会社にメールを送り、それぞれの会社から返信をもらう必要があります。
j 個目の会社に送るメールを書くには A_j 分の時間を要し、送ってから B_j 分後に返信が届きます。
高橋君は時刻 0 からメールを書き始めます。
高橋君は N 通のメールを好きな順番で書くことができますが、2 通以上のメールを同時に書くことはできません。
高橋君がすべての返信を受け取り終える時刻としてあり得る最小値を求めてください。
ただし、メールを送るのにかかる時間は無視できるものとします。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq Q \leq 10^5
  • 1 \leq A_j,B_j \leq 10^9
  • 各クエリにおいて、1 \leq i \leq N
  • 各クエリにおいて、1 \leq x \leq 10^9
  • 入力される値はすべて整数

入力

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

N Q  
A_1 A_2 \ldots A_N  
B_1 B_2 \ldots B_N  
\mathrm{query}_1  
\mathrm{query}_2  
\vdots  
\mathrm{query}_Q

各クエリ \mathrm{query}_q では、クエリの種類（1 か 2）と i と x がこの順に空白区切りで与えられる。
すなわち、各クエリは以下の 2 つの形式のいずれかである。

1 i x  

2 i x

出力

答えを合計 Q 行で出力せよ。 q 行目には、q 番目のクエリを処理した後の問題の答えを出力せよ。

入力例 1

3 3
4 6 7
4 6 7
1 2 1
2 3 7
2 3 1

出力例 1

16
16
13

最初のクエリを行った後、A=(4,1,7), \; B=(4,6,7) です。
時刻 0 に会社 3 に送るメールを書き始め、時刻 7 に書き終えて会社 3 にメールを送ると、時刻 14 に返信を受け取ります。
時刻 7 に会社 2 に送るメールを書き始め、時刻 8 に書き終えて会社 2 にメールを送ると、時刻 14 に返信を受け取ります。
時刻 8 に会社 1 に送るメールを書き始め、時刻 12 に書き終えて会社 1 にメールを送ると、時刻 16 に返信を受け取ります。

Score : 525 points

Problem Statement

You are given length-N sequences of positive integers A=(A_1,A_2,\dots,A_N) and B=(B_1,B_2,\dots,B_N).
You are given Q queries.
Each query is of one of the following two types.

  • 1 i x : Change A_i to x.
  • 2 i x : Change B_i to x.

After processing each query, solve the following problem.

Takahashi needs to send an email to each of N companies and receive a reply from each of them.
Writing the email to send to the j-th company takes A_j minutes, and the reply arrives B_j minutes after it is sent.
He starts writing emails at time 0.
He can write the N emails in any order he likes, but he cannot write two or more emails simultaneously.
Find the minimum possible time at which he finishes receiving all of the replies.
Assume that the time taken to send emails is negligible.

Constraints

  • 1 \leq N \leq 10^5
  • 1 \leq Q \leq 10^5
  • 1 \leq A_j,B_j \leq 10^9
  • In each query, 1 \leq i \leq N.
  • In each query, 1 \leq x \leq 10^9.
  • All input values are integers.

Input

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

N Q  
A_1 A_2 \ldots A_N  
B_1 B_2 \ldots B_N  
\mathrm{query}_1  
\mathrm{query}_2  
\vdots  
\mathrm{query}_Q

For each query \mathrm{query}_q, the type of the query (1 or 2), i, and x are given in this order, separated by spaces.
That is, each query is given in one of the following two formats:

1 i x  

2 i x

Output

Output the answers in a total of Q lines. The q-th line should contain the answer to the problem after processing the q-th query.

Sample Input 1

3 3
4 6 7
4 6 7
1 2 1
2 3 7
2 3 1

Sample Output 1

16
16
13

After processing the first query, A=(4,1,7) and B=(4,6,7).
If Takahashi starts writing the email to send to company 3 at time 0, finishes writing it at time 7, and sends it to company 3, he receives the reply at time 14.
If he starts writing the email to send to company 2 at time 7, finishes writing it at time 8, and sends it to company 2, he receives the reply at time 14.
If he starts writing the email to send to company 1 at time 8, finishes writing it at time 12, and sends it to company 1, he receives the reply at time 16.