题目背景

yummy 看到一些视频博主专门帮别人实现愿望，比如某博主会随机采访路人：“$100$ 块钱还是许个愿望？”

另一些博主则不同，会用接力的方式传递爱心。每次采访一个路人，都会给出上一个人描述的礼物，并询问自己应该给下一个人准备一个什么。

现在，考虑将两种方式结合起来，然后稍微改编一下，我们就有了这道题目。

本题和 EZ Version 的区别：加入了多组询问。

题目描述

现在有 $n$ 个路人，你已经知道了每个人的愿望价值 $a_i$ 和给下一个人准备的礼物价值 $b_i$。

我们定义，实现一次愿望，或选择上一个人的礼物，或者拿 $100$ 块钱，都被称为一次满足。

定义一次采访为选中这些路人中的若干人，重新编号为 $x_1,x_2,\ldots,x_k$，然后进行如下操作：

• 询问 $x_k$ 给第一个人的礼物价值 $b_{x_k}$。
• 对于每个 $i=1,2,\ldots,k$，询问 TA 要选择 $100$ 块钱，实现一个自己的愿望，还是选择上一个人描述的（注意不是上一个人出钱）礼物，并实现。
• 每次满足一个人后，询问希望你给下一个人准备的礼物。

现在要进行若干次采访，使得最终每个人都恰好被满足一次。假如每个人都会选择价格最高的满足方式，你需要安排采访，使得花费的总金额最低。

然而，心愿往往会膨胀。所以在回答完上面问题后，有 $q$ 次操作，每次输入两个数 $x,y$ 表示将 $a_x$ 增加 $y$。每次操作结束后，你都要重新计算最小花费。

输入格式

输入的第一行有两个正整数 $n,q$，表示人数和操作次数。

第二行是 $n$ 个正整数 $a_1,a_2,\ldots,a_n$ 表示心愿的价值。

第三行是 $n$ 个正整数 $b_1,b_2,\ldots,b_n$ 表示给下一个人礼物的价值。

之后 $q$ 行，每行两个整数 $x,y$ 表示一次操作。

输出格式

输出 $q+1$ 行，每行一个整数。第 $i$ 行表示第 $i$ 个操作前的最小花费；特别地最后一行是所有操作结束后的最小花费。

样例 #1

样例输入 #1

3 1
20 190 400
170 50 600
2 220

样例输出 #1

890
1100

样例 #2,3,4

点我下载大样例

提示

【样例解释】

在操作之前：

第一次采访采访 $1,2$ 两人，第二次采访路人 $3$。第一次采访有以下步骤：

1. 先询问路人 $2$ 发现希望给路人 $1$ 一份 $50$ 元礼物。
2. 然后路人 $1$ 可以从自己的 $20$ 元愿望、上一个人的 $50$ 元礼物以及 $100$ 元选一个，他选择 $100$ 元。
3. 询问路人 $1$ 得知他希望给下一个人 $170$ 元礼物。
4. 让路人 $2$ 从自己的 $190$ 元愿望、上一个人的 $170$ 礼物以及 $100$ 元现金中选一个。他选择 $190$ 元愿望。

第二次采访先询问最后一个人 $3$ 要给第一个人 $3$ 多少元礼物，得到答案 $600$。然后采访的第一个人 $3$ 可以从自己的 $400$ 元愿望、$600$ 元礼物和 $100$ 元现金中选出一个。他选择 $600$ 元礼物。

三个人总花费为 $100+190+600=890$ 元。可以证明没有代价更小的方案。

在操作之后，路人 $2$ 的心愿价值变成 $410$ 元。此时按照 $2,1,3$ 的顺序采访，满足路人 $2,1,3$ 依次花去 $600,100,400$ 元，合计 $1100$ 元。

【数据范围】

测试点编号	$n\le$	$q\le$	$a_i\le$	$b_i\le$	单个测试点分值
$1\sim 2$	$7$	$3$			$4$
$3\sim 4$	$16$
$5\sim 6$	$200$
$7$	$2\times 10^5$	$1$	$100$	$100$	$1$
$8$		$3$			$2$
$9\sim 10$					$5$
$11\sim 13$		$10^5$	$2\times 10^5$		$8$
$14\sim 16$	$10^5$	$5\times 10^4$			$7$
$17\sim 19$	$2\times 10^5$	$10^5$			$6$

上方表格中，留空表示和全体数据的范围一致。"$a_i\le$"一栏表示的是任意时刻 $a_i$ 不超过对应值。

对于全体数据，保证 $3\le n\le 2\times 10^5$，$1\le q\le 10^5$，$1\le x\le n$，任意时刻 $1\le a_i,b_i,y\le 10^9$。