← 返回题目列表

Codeforces · 1195/C

C. 篮球练习

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

SIS终于开放了篮球场,所以Demid决定举办一次篮球练习会。 $$$2 \cdot n$$$ 学生来到 Demid 的练习课上,他将他们排成大小相同的两排(每排正好有 $$$n$$$ 人)。每行中的学生按从左到右的顺序从 $$$1$$$ 到 $$$n$$$ 编号。

现在 Demid 想要选择一支球队来打篮球。他会从左到右选择球员,每个选择的球员(不包括第一个被选中的球员)的索引将严格大于先前选择的球员的索引。为了避免优先考虑某一行,德米德以这样的方式选择学生,即连续选择的学生不属于同一行。第一个学生可以从所有 $$$2n$$$ 学生中选择(没有额外的限制),并且一个团队可以由任意数量的学生组成。

Demid认为,为了组成一支完美的团队,他应该以这样的方式选择学生,即所有所选学生的总身高尽可能高。帮助德米德找到他可以选择的球队中球员的最大可能总高度。

输入

输入的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 每行中的学生人数。

输入的第二行包含 $$$n$$$ 整数 $$$h_{1, 1}, h_{1, 2}, \ldots, h_{1, n}$$$ ($$$1 \le h_{1, i} \le 10^9$$$),其中 $$$h_{1, i}$$$ 是第 $$$i$$$ 的高度第一排的学生。

输入的第三行包含 $$$n$$$ 整数 $$$h_{2, 1}, h_{2, 2}, \ldots, h_{2, n}$$$ ($$$1 \le h_{2, i} \le 10^9$$$),其中 $$$h_{2, i}$$$ 是第 $$$i$$$ 的高度第二排的学生。

输出

打印一个整数 - Demid 可以选择的球队中球员的最大可能总高度。

示例

输入 #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

注意

在第一个示例中,Demid 可以选择以下团队,如下所示:

在第二个示例中,Demid 可以选择以下团队,如下所示: