配点 : $700$ 点

問題文

長さ $2N$ の数列 $a,b$ が与えられます。$i$ 番目の要素はそれぞれ $a_i,b_i$ です。 すぬけくんはこの $2$ つの数列を使って長さ $2N$ の バランスの取れた括弧列 のペア $(s,t)$ の 美しさ を計算する仕事をしています。 美しさは以下のように計算されます。

• $X=0$ とする
• $1$ 以上 $2N$ 以下の全ての $i$ について、$s_i = t_i$ ならば $a_i$ を、そうでなければ $b_i$ を $X$ に加算する
• 最終的な $X$ の値が $(s,t)$ の美しさである

$Q$ 個のクエリが与えられるので順番に処理してください。 $i$ 番目のクエリでは $a_{p_i}$ を $x_i$ に、$b_{p_i}$ を $y_i$ に更新した後、バランスの取れた括弧列のペアの美しさとしてありうる値の最大値を求めてください。

この問題において、以下に示されるいずれかのみがバランスの取れた括弧列として定義されます。

• 空文字列
• バランスの取れた括弧列 $s$ について (,$s$, ) をこの順番で連結した文字列
• バランスの取れた括弧列 $s,t$ について $s,t$ をこの順番で連結した文字列

制約

• $1 \leq N,Q \leq 10^{5}$
• $-10^{9} \leq a_i,b_i,x_i,y_i \leq 10^{9}$
• $1 \leq p_i \leq 2N$
• 与えられる入力は全て整数

部分点

• $200$ 点分のデータセットでは $N \leq 5,Q \leq 10$ が成立する
• $300$ 点分のデータセットでは $Q=1$ が成立する

入力

入力は以下の形式で標準入力から与えられる。

$N$ $Q$

$a_1$ $a_2$ $...$ $a_{2N}$

$b_1$ $b_2$ $...$ $b_{2N}$

$p_1$ $x_1$ $y_1$

$:$

$p_Q$ $x_Q$ $y_Q$

出力

答えを $Q$ 行に出力せよ。$i$ 行目には $i$ 番目のクエリに対する応答を出力せよ。

2 2
1 1 7 3
4 2 3 3
2 4 6
3 2 5

15
15

• $1$ 番目のクエリにより、$a=(1,4,7,3),b=(4,6,3,3)$ となります。$(s,t) =($()(),()()$)$ のとき、美しさが $15$ となり、これが最大です。
• $2$ 番目のクエリにより、$a=(1,4,2,3),b=(4,6,5,3)$ となります。$(s,t) =($()(),(())$)$ のとき、美しさが $15$ となり、これが最大です。

7 7
34 -20 -27 42 44 29 9 11 20 44 27 19 -31 -29
46 -50 -11 20 28 46 12 13 33 -22 -48 -27 35 -17
7 27 34
12 -2 22
4 -50 -12
3 -32 15
8 -7 23
3 -30 11
4 -2 23

311
312
260
286
296
292
327