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 可以选择以下团队,如下所示: