D - Tail of Snake 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

すぬけ君は蛇を観察しており、どこからどこまでが頭・胴・尾なのかが気になっています。 すぬけ君は蛇を 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) が与えられます。

整数の組 (x, y) が 1 \leq x < y < N を満たすとき、\displaystyle\sum_{i = 1}^{x} A_i + \sum_{i = x + 1}^{y} B_i + \sum_{i = y + 1}^{N} C_i の値として取り得る最大値を求めてください。

制約

  • 3 \leq N \leq 3 \times 10^5
  • 1 \leq A_i, B_i, C_i \leq 10^6
  • 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

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

出力

答えを出力せよ。

入力例 1

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

出力例 1

16

(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 となります。

入力例 2

3
1 1 1
1 1 1
1 1 1

出力例 2

3

入力例 3

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

出力例 3

50

Score : 400 points

Problem Statement

Snuke is observing a snake and is curious about which parts are the head, body, and tail. He divided the snake into N blocks and evaluated the head-likeness, body-likeness, and tail-likeness of each block. Then, he decided to find the division that maximizes the sum of the likeness values.

You are given length-N integer sequences A = (A_1, A_2, \ldots, A_N), B = (B_1, B_2, \ldots, B_N), and C = (C_1, C_2, \ldots, C_N).

Find the maximum possible value of \displaystyle\sum_{i = 1}^{x} A_i + \sum_{i = x + 1}^{y} B_i + \sum_{i = y + 1}^{N} C_i for a pair of integers (x, y) satisfying 1 \leq x < y < N.

Constraints

  • 3 \leq N \leq 3 \times 10^5
  • 1 \leq A_i, B_i, C_i \leq 10^6
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Output the answer.

Sample Input 1

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

Sample Output 1

16

With (x, y) = (2, 3), we have \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.

Sample Input 2

3
1 1 1
1 1 1
1 1 1

Sample Output 2

3

Sample Input 3

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

Sample Output 3

50