题目描述

某同学要为连续的 $n+1$ 次小测做准备，编号从 $1$ 到 $n+1$，他一共有 $n$ 天复习时间。第 $i$ 天，他只能选择复习第 $i$ 次或第 $i+1$ 次小测的内容。

每次小测最多复习两次：第 $i$ 次小测的第一次复习可以提高 $a_i$ 分，第二次复习可以提高 $b_i$ 分。请帮他安排每天的复习对象，使提高的总分最大。

输入格式

第一行一个正整数 $n$。

第二行 $n+1$ 个正整数，依次表示 $a_1,a_2,\dots,a_{n+1}$。

第三行 $n+1$ 个正整数，依次表示 $b_1,b_2,\dots,b_{n+1}$。

输出格式

输出一个整数，表示最大可提高的总分。

样例

4
3 9 4 8 2
7 1 6 5 10

27

2
1 100 1
1 1 1

101

1
9 4
2 3

9

样例解释

样例 1 中，一种最优安排是第 1 天复习第 2 次（$+9$）、第 2 天复习第 3 次（$+4$）、第 3 天再次复习第 3 次（$+6$）、第 4 天复习第 4 次（$+8$），共 $27$ 分。

样例 2 中，第 1 天复习第 2 次小测得到 $100$，第 2 天再复习第 2 次得到 $1$，共 $101$ 分。

样例 3 中只有一天，选择收益更高的第 1 次小测，得 $9$ 分。

数据范围与约定

对于 $100\%$ 的数据，$1\le n\le 10^6$，$1\le a_i,b_i\le 100$。