零食最佳吃法

题目描述

小明收到了一个有 N 个格子的零食礼盒，每个格子里都装着一款特色零食。这款零食有三种吃法，每种吃法能带来不同的满足度：

• 直接拆开吃（吃法 $A$）：第 i 个格子的零食带来 $A_i$ 点满足度；
• 分享给同桌吃（吃法 $B$）：第 i 个格子的零食带来 $B_i$ 点满足度；
• 留到周末吃（吃法 $C$）：第 i 个格子的零食带来 $C_i$ 点满足度。

小明想把礼盒里的零食分成三部分，按顺序分别用三种吃法解决，具体要求是：

1. 前 x 个格子（$1≤x<y<N$）：全部直接拆开吃；
2. 中间 x+1 到 y 个格子（$x<y$）：全部分享给同桌吃；
3. 最后 y+1 到 N 个格子（$y<N$）：全部留到周末吃。

形式化的，请你帮小明找到满足条件的 $x$ 和 $y$，让 $\sum_{i=1}^x A_i$ + $\sum_{i=x+1}^y B_i$ + $\sum_{i=y+1}^N C_i$ 最大。

输入格式

第一行包含一个整数 $N（3≤N≤3×10^5）$，表示礼盒的格子数。 第二行包含 $N$ 个整数 $A_1, A_2, ..., A_N（1 \leq A_i \leq 10^9）$，表示每个格子零食“直接吃”的满足度。 第三行包含 $N$ 个整数 $B_1, B_2, ..., B_N（1 \leq B_i \leq 10^9）$，表示每个格子零食“分享吃”的满足度。 第四行包含 $N$ 个整数 $C_1, C_2, ..., C_N（1 \leq C_i \leq 10^9）$，表示每个格子零食“留着吃”的满足度。

输出格式

输出一个整数，表示满足条件的最大满足度总和。

样例 1

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

16

样例 2

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

50

提示

对于第一个样例，选择 $x=2$ 和 $y=3$，满足度总和为 $A_1 + A_2 + B_3 + C_4 + C_5 = 16$（即 $1+4+4+4+3=16$）。