AT_aalc001_x 不揃いさ

You are given sequences of nonnegative integers $ A=(A_1,A_2,\ldots,A_N) $ and $ g=(g_1,g_2,\ldots,g_N) $ of length $ N $ , and a sequence of integers $ d=(d_1,d_2,\ldots,d_{N-1}) $ of length $ N-1 $ . Note that $ g_j $ satisfies $ 1 \leq g_j \leq 2 $ . Using the sequences $ g,d $ , define $ f(B) $ for a sequence of integers $ B=(B_1,B_2,\ldots,B_N) $ of length $ N $ as follows. You may freely choose a sequence of integers $ C=(C_1,C_2,\ldots,C_N) $ of length $ N $ . Define the cost of $ B $ and $ C $ as \\\[ \\sum\_{j=1}^{N} g\_j |B\_j-C\_j|+\\sum\_{j=1}^{N-1} d\_j |C\_j-C\_{j+1}| \\\] Then, $ f(B) $ is the minimum cost over all possible choices of the integer sequence $ C $ . Process the following $ Q $ queries in order. In query $ k $ , you are given integers $ i_k,x_k $ . Change $ A_{i_k} $ to $ x_k $ and calculate $ f(A) $ .

The input is given from Standard Input in the following format: > $ 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 $

Print $ Q $ lines. The $ k $ -th line should contain $ f(A) $ calculated in query $ k $ .

### Sample Explanation 1 After query $ 1 $ , $ A=(1,3,2) $ . For example, choosing $ C=(2,2,2) $ gives a cost of $ 3 $ . The cost cannot be made less than $ 3 $ , so $ f(A)=3 $ . ### Sample Explanation 2 When all elements of $ A $ are equal, choosing $ C=A $ gives a cost of $ 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 $ - All numerical values in the input are integers.