分数: 700 点
问题陈述
在这个问题中,我们考虑由以下组成的字符串 (, ), [,和 ].
一个字符串 x 据说是 好的括号序列 当且仅当 一 满足以下条件的 :
- x 是一个空序列。
- 有一个很好的括号序列 s 这样连接
(, s,和)按此顺序会导致 x. - 有一个很好的括号序列 s 这样连接
[, s,和]按此顺序会导致 x. - 有非空好括号序列 s 和 t 这样连接 s 和 t 按此顺序会导致 x.
例如, [], ([()]),和 ()[()] 是很好的括号序列,但两者都不是 ()) 也不 ([)] 是一个很好的括号序列。
给出的是偶数 N 和整数序列 A 和 B 长度 N 每个。 在这里,我们为长度良好的括号序列定义一个分数 N, s=s_1s_2\cdots s_N,如下:
- 的分数 s 是其字符的分数总和。
- 的分数 i- 第一个字符 (
字符串的1 \leq i \leq N) 是 A_i if s_i is
(or),和 B_i if s_i is[or].
找到长度合适的括号序列的最大可能得分 N.
约束
- 2 \leq N \leq 10^5
- N 是偶数。
- 1 \leq A_i \leq 10^9
- 1 \leq B_i \leq 10^9
- 输入的所有数字均为整数。
输入
输入由标准输入按以下格式给出:
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
示例输出 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