AT_aalc001_x 不揃いさ

長さ $ 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) $ を出力せよ。

### Sample Explanation 1 $ 1 $ 番目のクエリの後、 $ A=(1,3,2) $ です。例えば $ C=(2,2,2) $ とするとコストは $ 3 $ になります。コストを $ 3 $ より小さくすることはできないため、 $ f(A)=3 $ です。 ### Sample Explanation 2 $ A $ のすべての要素が等しいとき、 $ C=A $ とすることでコストを $ 0 $ にできます。 ### Constraints - $ 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 $ - 入力される数値はすべて整数