AT_abc438_d.[ABC438D] Tail of Snake

Snuke 正在观察一条蛇，他很好奇蛇的头部、蛇身和蛇尾分别是哪个部分。他把蛇分成了 $N$ 块，并评估了每个块的头部相似度、身体相似度和尾部相似度。然后，他决定找出使相似值总和最大的分割方法。

给你长度为 $N$ 的整数序列 $A = (A_1, A_2, \ldots, A_N)$ 、 $B = (B_1, B_2, \ldots, B_N)$ 和 $C = (C_1, C_2, \ldots, C_N)$ 。

求满足 $1 \le x < y < N$ 的一对整数 $(x, y)$ ，最大化 $\displaystyle\sum_{i = 1}^{x} A_i + \sum_{i = x + 1}^{y} B_i + \sum_{i = y + 1}^{N} C_i$ 的值。

输入内容由标准输入法提供，格式如下

$N\\$
$A_1$ $A_2$ $\ldots$ $A_N\\$
$B_1$ $B_2$ $\ldots$ $B_N\\$
$C_1$ $C_2$ $\ldots$ $C_N$

输出答案。

数据范围

• $3 \leq N \leq 3 \times 10^5$
• $1 \leq A_i, B_i, C_i \leq 10^6$
• 所有输入值均为整数。

样例解释 1

选择 $(x, y) = (2, 3)$ ，我们得到 $\displaystyle\sum_{i = 1}^{x} A_i + \sum_{i = x + 1}^{y} B_i + \sum_{i = y + 1}^{N} C_i = 1 + 4 + 4 + 4 + 3 = 16$ 。