← 返回题目列表

AtCoder · arc090_a

C. 糖果

中文机器翻译题面 查看原题

分数: 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 次,然后向下移动一次,然后向右移动一次。

示例输入 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