← 返回题目列表

AtCoder · agc048_b

B. 括号分数

中文机器翻译题面 查看原题

分数: 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