AT_agc048_b [AGC048B] Bracket Score

在本题中，我们考虑由 `(`、`)`、`[`、`]` 组成的字符串。 当字符串 $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$

请输出答案。

## 限制条件 - $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 翻译