AT_abc467_f.Email Scheduling Optimization

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.

给你两个长度为 $N$ 的正整数序列 $A=(A_1,A_2,\dots,A_N)$ 和 $B=(B_1,B_2,\dots,B_N)$。
你将收到 $Q$ 个查询。
每个查询属于以下两种类型之一：

• 1 i x：将 $A_i$ 修改为 $x$。
• 2 i x：将 $B_i$ 修改为 $x$。

在处理完每个查询后，请解决如下问题：

高桥需要向 $N$ 家公司分别发送一封电子邮件，并从每家公司各收到一封回信。
向第 $j$ 家公司发送邮件需耗时 $A_j$ 分钟，且该邮件发出后 $B_j$ 分钟会收到回信。
他从时刻 $0$ 开始撰写邮件。
他可以按任意顺序撰写这 $N$ 封邮件，但不能同时撰写多封邮件。
求他收齐所有回信的最早可能时刻。
假设发送邮件本身所需时间可忽略不计。

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$

输入从标准输入给出，格式如下：

$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$，以空格分隔。
即，每个查询以以下两种格式之一给出：

$1$ $i$ $x$

$2$ $i$ $x$

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.

在总共 $Q$ 行中输出答案。第 $q$ 行应包含处理完第 $q$ 个查询后的答案。

Sample 1 Explanation:
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$.

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.

样例 1 解释：
处理第一个查询后，$A=(4,1,7)$，$B=(4,6,7)$。
若高桥在时刻 $0$ 开始撰写发给公司 $3$ 的邮件，于时刻 $7$ 完成撰写并发出，则他在时刻 $14$ 收到回复。
若他在时刻 $7$ 开始撰写发给公司 $2$ 的邮件，于时刻 $8$ 完成撰写并发出，则他在时刻 $14$ 收到回复。
若他在时刻 $8$ 开始撰写发给公司 $1$ 的邮件，于时刻 $12$ 完成撰写并发出，则他在时刻 $16$ 收到回复。

限制条件

• $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$。
• 所有输入值均为整数。