You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

初一竞赛组期末考题

Description

给定一个$2*n$的数字矩阵，用$n$个一半黑色一半透明的$1*2$骨牌将矩阵全部覆盖，骨牌不能有重叠，不能有数字不被覆盖。此时有$n$个数被黑色盖住，另外$n$个数可以看见。求可以看见的数字的和的最大值。

Format

Input

第一行一个正整数$n$，第二行$n$个数为矩阵第一行，第三行$n$个数为矩阵第二行。

Output

一个正整数表示最大和。

Samples

3
4 2 1
4 2 1

9

3
4 3 1
4 3 1

10

Limitation

对20%的数据，$n≤100$。

对50%的数据，$n≤10000$。

对100%的数据，$3≤n≤3*10^5$，矩阵中所有元素的值非负且不超过$10^9$。

1s, 1024KiB for each test case.