回信时刻（mail）

题目描述

Y 同学需要依次给 $N$ 家公司发送邮件，并等待每家公司回复。

给第 $i$ 家公司撰写邮件需要 $A_i$ 分钟。邮件发送后，还需要等待 $B_i$ 分钟才能收到该公司的回复。发送邮件本身所需的时间忽略不计。

Y 同学从时刻 $0$ 开始撰写邮件。所有邮件可以按照任意顺序撰写，但任意时刻至多只能撰写一封邮件。已经发送的邮件可以在 Y 同学撰写其他邮件时等待回复。

现在有 $Q$ 次修改。每次修改会改变某个 $A_i$ 或 $B_i$。在每次修改完成后，请求出一种最优的邮件撰写顺序，使收到全部回复的时刻尽可能早，并输出这一最早时刻。

输入格式

第一行包含两个正整数 $N,Q$，分别表示公司数量和修改次数。

第二行包含 $N$ 个正整数 $A_1,A_2,\ldots,A_N$。

第三行包含 $N$ 个正整数 $B_1,B_2,\ldots,B_N$。

接下来 $Q$ 行，每行包含三个整数 $op,i,x$，表示一次修改：

• 当 $op=1$ 时，将 $A_i$ 修改为 $x$。
• 当 $op=2$ 时，将 $B_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

数据范围与约定

对于 $100\%$ 的数据，保证：

共有 $22$ 个正式测试点。

特殊性质 A：在初始状态和每次修改后，所有 $B_i$ 均相等。

特殊性质 B：所有修改操作均满足 $op=1$。