篮球训练

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

有 $2n$ 名学生站成两排，每排恰好有 $n$ 人。每排学生从左到右编号为 $1$ 到 $n$，第 $r$ 排第 $i$ 名学生的身高为 $h_{r,i}$。

你需要从左到右选择若干名学生组成队伍。除第一名被选学生外，每名被选学生的编号都必须严格大于上一名被选学生的编号；并且不能连续选择同一排的学生。队伍人数没有限制，也可以跳过任意学生。

求所选学生身高总和的最大值。

输入格式

第一行包含一个整数 $n$。

第二行包含 $n$ 个整数 $h_{1,1},h_{1,2},\ldots,h_{1,n}$。

第三行包含 $n$ 个整数 $h_{2,1},h_{2,2},\ldots,h_{2,n}$。

输出格式

输出一个整数，表示最大身高总和。

样例输入 1

5
9 3 5 7 3
5 8 1 4 5

样例输出 1

29

样例输入 2

3
1 2 9
10 1 1

样例输出 2

19

样例输入 3

1
7
4

样例输出 3

7

数据范围

对于所有数据，$1\le n\le 10^5$，$1\le h_{r,i}\le 10^9$。