配点 : $300$ 点

問題文

$2 \times N$ のマス目があります。上から $i$ 行目、左から $j$ 列目 ($1 \leq i \leq 2$, $1 \leq j \leq N$) のマスをマス $(i, j)$ と表すことにします。

あなたははじめ、左上のマス $(1, 1)$ にいます。 あなたは、右方向または下方向への移動を繰り返し、右下のマス $(2, N)$ に移動しようとしています。

マス $(i, j)$ には $A_{i, j}$ 個のアメが置かれています。 あなたは移動中に通ったマスに置いてあるアメをすべて回収します。 左上および右下のマスにもアメが置かれており、あなたはこれらのマスに置かれているアメも回収します。

移動方法をうまく選んだとき、最大で何個のアメを回収できるでしょうか。

制約

• $1 \leq N \leq 100$
• $1 \leq A_{i, j} \leq 100$ ($1 \leq i \leq 2$, $1 \leq j \leq N$)

入力

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

$N$

$A_{1, 1}$ $A_{1, 2}$ $...$ $A_{1, N}$

$A_{2, 1}$ $A_{2, 2}$ $...$ $A_{2, N}$

出力

回収できるアメの個数の最大値を出力せよ。

5
3 2 2 4 1
1 2 2 2 1

14

以下のように移動するとき、回収できるアメの個数が最大となります。

• まず右に $3$ 回移動する。その後下に $1$ 回移動し、さらに右に $1$ 回移動する。

4
1 1 1 1
1 1 1 1

5

どのように移動しても回収できるアメの個数は同じになります。

7
3 3 4 5 4 5 3
5 3 4 4 2 3 2

29

1
2
3

5