AT_aalc001_x.Unevenness

给你两个长度为 $N$ 的非负整数序列 $A=(A_1,A_2,\ldots,A_N)$ 和 $g=(g_1,g_2,\ldots,g_N)$，以及一个长度为 $N-1$ 的整数序列 $d=(d_1,d_2,\ldots,d_{N-1})$。注意，每个 $g_j$ 满足 $1 \leq g_j \leq 2$。

利用序列 $g$ 和 $d$，对任意长度为 $N$ 的整数序列 $B=(B_1,B_2,\ldots,B_N)$ 定义函数 $f(B)$ 如下：

你可以任选一个长度为 $N$ 的整数序列 $C=(C_1,C_2,\ldots,C_N)$。定义 $B$ 与 $C$ 的代价为

[
\sum_{j=1}^{N} g_j |B_j-C_j|+\sum_{j=1}^{N-1} d_j |C_j-C_{j+1}|
]

那么，$f(B)$ 即为在所有可能的整数序列 $C$ 中，上述代价的最小值。

请依次处理以下 $Q$ 个查询。

在第 $k$ 个查询中，你将收到两个整数 $i_k$ 和 $x_k$。将 $A_{i_k}$ 修改为 $x_k$，然后计算 $f(A)$。

输入从标准输入中按以下格式给出：

$N$ $Q$
$A_1$ $A_2$ $\ldots$ $A_N$
$g_1$ $g_2$ $\ldots$ $g_N$
$d_1$ $d_2$ $\ldots$ $d_{N-1}$
$i_1$ $x_1$
$i_2$ $x_2$
$\vdots$
$i_Q$ $x_Q$

输出 $Q$ 行。第 $k$ 行应包含第 $k$ 个查询中计算得到的 $f(A)$。

样例 1 解释：
执行查询 $1$ 后，$A=(1,3,2)$。例如，选择 $C=(2,2,2)$ 可得到代价为 $3$。代价无法低于 $3$，因此 $f(A)=3$。

样例 2 解释：
当 $A$ 的所有元素均相等时，选择 $C=A$ 可得到代价 $0$。

约束条件

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq Q \leq 2 \times 10^5$
• $0 \leq A_j \leq 10^9$
• $1 \leq g_j \leq 2$
• $1 \leq d_j \leq 10^9$
• $1 \leq i_k \leq N$
• $0 \leq x_k \leq 10^9$
• 输入中的所有数值均为整数。