/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 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}
出力
回収できるアメの個数の最大値を出力せよ。
入力例 1
5 3 2 2 4 1 1 2 2 2 1
出力例 1
14
以下のように移動するとき、回収できるアメの個数が最大となります。
- まず右に 3 回移動する。その後下に 1 回移動し、さらに右に 1 回移動する。
入力例 2
4 1 1 1 1 1 1 1 1
出力例 2
5
どのように移動しても回収できるアメの個数は同じになります。
入力例 3
7 3 3 4 5 4 5 3 5 3 4 4 2 3 2
出力例 3
29
入力例 4
1 2 3
出力例 4
5
Score : 300 points
Problem Statement
We have a 2 \times N grid. We will denote the square at the i-th row and j-th column (1 \leq i \leq 2, 1 \leq j \leq N) as (i, j).
You are initially in the top-left square, (1, 1). You will travel to the bottom-right square, (2, N), by repeatedly moving right or down.
The square (i, j) contains A_{i, j} candies. You will collect all the candies you visit during the travel. The top-left and bottom-right squares also contain candies, and you will also collect them.
At most how many candies can you collect when you choose the best way to travel?
Constraints
- 1 \leq N \leq 100
- 1 \leq A_{i, j} \leq 100 (1 \leq i \leq 2, 1 \leq j \leq N)
Input
Input is given from Standard Input in the following format:
N
A_{1, 1} A_{1, 2} ... A_{1, N}
A_{2, 1} A_{2, 2} ... A_{2, N}
Output
Print the maximum number of candies that can be collected.
Sample Input 1
5 3 2 2 4 1 1 2 2 2 1
Sample Output 1
14
The number of collected candies will be maximized when you:
- move right three times, then move down once, then move right once.
Sample Input 2
4 1 1 1 1 1 1 1 1
Sample Output 2
5
You will always collect the same number of candies, regardless of how you travel.
Sample Input 3
7 3 3 4 5 4 5 3 5 3 4 4 2 3 2
Sample Output 3
29
Sample Input 4
1 2 3
Sample Output 4
5