AT_kupc2020_e.Sequence Partitioning

给定三个长度为 $N$ 的整数数列 $A=(a_0,\ldots,a_{N-1})$、$B=(b_0,\ldots,b_{N-1})$、$C=(c_0,\ldots,c_{N-1})$，其中每个元素都在 $-10^9$ 到 $10^9$ 之间。

现在，考虑将数列 $A$ 分割成若干个连续的子序列。一次分割可以用满足以下 $3$ 个条件的整数序列 $D=(d_0,\ldots,d_r)$ 来表示：

• $d_0=0$。
• $d_r=N$。
• 对于 $0\leq i<r$，有 $d_i<d_{i+1}$。

也就是说，每个 $i$ 对应的区间 $[d_i,d_{i+1})$ 表示一个连续区间，整个数列被这 $r$ 个区间完全覆盖且不重叠。

对于一次分割 $D$，定义其得分函数 $f$ 如下：

$$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$ 的值最大，并输出该最大值。

输入通过标准输入给出，格式如下：

$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\leq N\leq 2\times 10^5$。
• $-10^9\leq a_i,b_i,c_i\leq 10^9\ (0\leq i<N)$。

样例解释 1

当 $D=(0,2)$ 时，得分为 $b_0+c_1+a_0+a_1=-3$。当 $D=(0,1,2)$ 时，得分为 $\min(b_0+c_0+a_0,b_1+c_1+a_1)=\min(1,1)=1$。

样例解释 2

请注意防止溢出。

由 ChatGPT 4.1 翻译