题目描述

在这个问题中，我们考虑由 (、)、[ 和 ] 组成的字符串。

一个字符串 $x$ 被称为良好的括号序列，当且仅当满足以下条件之一时：

• $x$ 是一个空序列。
• 存在一个良好的括号序列 $s$，连接 (、$s$ 和 ) 的结果是 $x$。
• 存在一个良好的括号序列 $s$，连接 [、$s$ 和 ] 的结果是 $x$。
• 存在非空的良好括号序列 $s$ 和 $t$，连接 $s$ 和 $t$ 的结果是 $x$。

例如，[]、([()]) 和 ()[()] 都是良好的括号序列，但 ()) 和 ([)] 都不是良好的括号序列。

给定一个偶数 $N$ 和两个长度为 $N$ 的整数序列 $A$ 和 $B$。在这里，我们定义长度为 $N$ 的良好括号序列 $s=s_1s_2\cdots s_N$ 的得分如下：

• $s$ 的得分是其字符得分的总和。
• 第 $i$ 个字符（$1 \leq i \leq N$）的得分是如果 $s_i$ 是 ( 或 ) 则为 $A_i$，如果 $s_i$ 是 [ 或 ] 则为 $B_i$。

找出长度为 $N$ 的良好括号序列的最大可能得分。

约束条件

• $2 \leq N \leq 10^5$
• $N$ 是一个偶数。
• $1 \leq A_i \leq 10^9$
• $1 \leq B_i \leq 10^9$
• 输入中的所有数字都是整数。

输入

输入以以下格式从标准输入给出。输入的第一行是：

$N$

接下来两行，每行包含 $N$ 个整数，表示序列 $A$ 和 $B$。

输出

打印答案。

示例输入 1

4
4 2 3 1
2 3 2 4

示例输出 1

12

对于 $s=$`()[]$，得分为$A_1+A_2+B_3+B_4=12$，这是最大可能的值。

示例输入 2

10
866111664 844917655 383133839 353498483 472381277 550309930 378371075 304570952 955719384 705445072
178537096 218662351 231371336 865935868 579910117 62731178 681212831 16537461 267238505 318106937

示例输出 2

6629738472