题目描述

校史馆新做了一组双排货架。货架分上下两行，每行有 $n$ 个格子，第 $r$ 行第 $c$ 列的格子用来放一件展品，能给展区带来 $v_{r,c}$ 点人气。

展品放得太密会互相遮挡，所以有规矩：任意两个有公共边的格子（上下相邻，或者左右相邻）不能同时放展品。斜着只挨一个角的两个格子不算有公共边，可以同时放。

现在程老师要在这组货架上挑一些格子放展品，让带来的人气总和最大。请你算一算这个最大值。

输入格式

从文件 shelf.in 中读入数据。

第一行一个整数 $n$，表示每行的格子数。

第二行 $n$ 个整数，依次表示第一行从左到右各格的人气值。

第三行 $n$ 个整数，依次表示第二行从左到右各格的人气值。

输出格式

输出到文件 shelf.out 中。

一行一个整数，表示人气总和的最大值。

数据范围

特殊性质 A：每个格子的人气值都不超过 $10$。

特殊性质 B：每个格子的人气值都等于 $1$。

对于所有测试点：$1 \le n \le 10^5$，$1 \le v_{r,c} \le 10^3$。

3
1 2 3
4 5 6

12

1
5
3

5

样例解释

样例 1：第 $1$ 列放下格（$4$ 点），第 $2$ 列放上格（$2$ 点），第 $3$ 列放下格（$6$ 点），总和是 $4 + 2 + 6 = 12$。这三格两两都没有公共边：第 $1$ 列下格与第 $2$ 列下格才是左右相邻的，而第 $2$ 列放的是上格；同样地，第 $2$ 列上格与第 $3$ 列上格相邻，而第 $3$ 列放的是下格。

样例 2：只有一列，上下两格有公共边，不能同时放，所以取人气值较大的上格，得到 $5$ 点。