描述

一条蛇被分成了 N 个块，每个块有三个属性值：头似度 A_i、身似度 B_i 和尾似度 C_i。我们需要将蛇划分为三部分：头部（前 x 块）、身体（第 x+1 到 y 块）和尾巴（第 y+1 到 N 块），其中 1 ≤ x < y < N。

目标是最大化总得分：

∑{i=1}^{x} A_i + ∑{i=x+1}^{y} B_i + ∑_{i=y+1}^{N} C_i

给定序列 A, B, C，求最大可能的得分。

输入输出格式

输入

第一行一个整数 N，表示蛇的块数。 第二行 N 个整数，表示序列 A。 第三行 N 个整数，表示序列 B。 第四行 N 个整数，表示序列 C。

输出

输出一个整数，表示最大得分。

样例

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

16

限制

• 3 ≤ N ≤ 3×10^5
• 1 ≤ A_i, B_i, C_i ≤ 10^6
• 所有输入均为整数