篮球训练 - 代码源竞赛平台

题目描述

蜗蜗准备进行 $N$ 轮篮球训练。训练记录可以看成一个 $2\times N$ 的表格，第 $i$ 列的上方和下方分别有一个分数。

蜗蜗可以选择若干个格子，但任意两个被选中的格子不能有公共边。被选中的格子分数之和越大越好，请你求出能够得到的最大分数。

输入格式

第一行包含一个整数 $N$，表示表格的列数。

第二行包含 $N$ 个整数，表示上方一行的分数。

第三行包含 $N$ 个整数，表示下方一行的分数。

输出格式

输出一行一个整数，表示最大分数。

样例

5
1 2 3 4 5
5 4 3 2 1

15

样例解释

一种最优选择是上方第 1、3、5 列和下方第 2、4 列的格子，所选分数之和为 $1+3+5+4+2=15$。

数据范围

对于 100% 的数据，保证 $1\le N\le10^5$，表格中的每个分数均为不超过 $10^5$ 的非负整数。