题目描述

Passenger 面临着连续的 $n + 1$ 场考试，编号从 $1$ 到 $n + 1$。 他有 $n$ 天时间复习。第 $i$ 天，他可以选择复习第 $i$ 或 $i + 1$ 场考试的内容。 显然一场考试最多可以被复习两次。对于第 $i$ 场考试，第一次复习可以提高 $a_i$ 分，第二次复习可以提高 $b_i$ 分。一场考试被复习两次之后总共提高 $a_i + b_i$ 分。 Passenger 想要最大化提升的分数和。

输入格式

第一行一个正整数 $n$。 第二行 $n + 1$ 个正整数 $a_1, a_2, \dots, a_n, a_{n+1}$。 第三行 $n + 1$ 个正整数 $b_1, b_2, \dots, b_n, b_{n+1}$。

输出格式

输出一行一个整数，表示答案。

输入输出样例

数据范围

• 对于 $20\%$ 的数据，保证 $n \leqslant 20$；
• 对于 $40\%$ 的数据，保证 $n \leqslant 10^3$；
• 对于 $100\%$ 的数据，保证 $1 \leqslant n \leqslant 10^6$，$1 \leqslant a_i, b_i \leqslant 100$。