配点 : 300 点
問題文
-10^9 以上 10^9 由以下整数构成,长度为 N 序列 使用 A=(a_0,...,a_{N-1}),B=(b_0,...,b_{N-1}),C=(c_0,...,c_{N-1}) 。 满足
现在,数列 A 分割为几个连续的子序列。分割是由满足以下 3 条件的整数序列 D=(d_0,...,d_r) 表示的。也就是说,每个
- d_0=0
- d_r=N
- d_i < d_{i+1} (0 \leq i < r)
表示一个连续区间,整个数列是这 i , [d_i,d_{i+1}) 个区间的并集。对于 r 返回 sukua 的函数
分割 D 针对…返回sukoa的函数 f 定义如下。 当巧妙地选择
\displaystyle f(D)=\min_{0 \leq i < r}\left\{b_{d_i}+c_{d_{i+1}-1}+\sum_{d_i \leq j < d_{i+1}} a_j\right\}
分割时, 请找到f 的最大值。 当
制約
- 所有输入均为整数。
- 1 \leq N \leq 2 \times 10^5
- -10^9 \leq a_i,b_i,c_i \leq 10^9(0 \leq i < N)
入力
输入是按以下格式从标准输入给出的。
N
a_0 a_1 \cdots a_{N-1}
b_0 b_1 \cdots b_{N-1}
c_0 c_1 \cdots c_{N-1}
出力
答案 行 1 行。
入力例 1
2 1 -1 -1 4 1 -2
出力例 1
1
D=(0,2) 时,sukoa 是 b_0+c_1+a_0+a_1=-3 。
D=(0,1,2) 时,sukoa 是 \min(b_0+c_0+a_0,b_1+c_1+a_1)=\min(1,1)=1 。
入力例 2
1 1000000000 1000000000 1000000000
出力例 2
3000000000
小心溢出。
入力例 3
11 -323225375 -897098227 -795978453 501188072 409939326 -362890219 969123048 962633819 252457646 694824070 -406990840 -696821643 -663750226 -570551722 670541392 172964990 399404695 -305728788 -157617655 -801518744 -328729631 -160335217 -465411342 -660775657 515997870 -34787742 628368976 84800619 -728713779 573207953 115652694 -686953578 -215986240
出力例 3
91174984