题目描述

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

当字符串 $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$ 的分数如下：

• $s$ 的分数为各个字符分数的总和。
• 第 $i$ 个字符（$1\leq i\leq N$）的分数：若 $s_i$ 是 ( 或 )，则为 $A_i$；若 $s_i$ 是 [ 或 ]，则为 $B_i$。

请你求出长度为 $N$ 的良好括号序列可能取得的最大分数。

输入格式

输入按以下格式从标准输入给出：

$N$ $A_1$ $A_2$ $\cdots$ $A_N$ $B_1$ $B_2$ $\cdots$ $B_N$

输出格式

请输出答案。

样例 1

输入

4
4 2 3 1
2 3 2 4

输出

12

样例 2

输入

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

输出

6629738472

说明/提示

限制条件

• $2\leq N\leq 10^5$
• $N$ 是偶数
• $1\leq A_i\leq 10^9$
• $1\leq B_i\leq 10^9$
• 所有输入的数均为整数。

样例解释 1

当 $s= ()[]$ 时，分数为 $A_1+A_2+B_3+B_4=12$，这是最大的分数。

由 ChatGPT 4.1 翻译