题目描述

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$

输出格式

输出答案。

输入输出样例 #1

输入 #1

5
1 4 2 4 3
2 3 4 2 2
3 2 4 4 3

输出 #1

16

输入输出样例 #2

输入 #2

3
1 1 1
1 1 1
1 1 1

输出 #2

3

输入输出样例 #3

输入 #3

6
2 10 7 7 7 11
5 7 9 10 9 12
6 6 7 10 12 7

输出 #3

50

说明/提示

数据范围

• $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$ 。