你手里有一个长度为
在你眼中,不同的括号序列带来的视觉美感不尽相同。因此,你对具有某一种结构的括号序列特别喜欢,而讨厌具有其他一些结构的括号序列。你希望对
具体而言,形如 (A()B)
(其中 A
, B
均为合法括号序列,下同)的结构是你喜欢的,而形如 (A)(B)
的结构是你不喜欢的。你有两种操作来改变括号之间的位置。
这两种操作如下:
- 操作 p(A)(B)q
的串中 A
和 B
之间的两个括号,变换为 p(A()B)q
(其中 p
, q
为任意串,可以为空,但不一定分别为合法括号序列,下同),它的代价为 (A)
中第一个左括号的权值加上 (B)
中第一个左括号的权值,其中 pABq
的串中的 A
和 B
,变换为 pBAq
,这个操作不需要代价。
注意:交换的时候所有左括号的权值是跟着这个括号一起交换的。
你现在想知道的是,将
输入格式
第一行三个整数
第二行一个长度为
第三行
输出格式
一行一个整数,表示把
样例一
input
2 0 1 ()() 1 3
output
1
explanation
最优方案是先使用操作 A
, B
, p
, q
都是空串)交换中间的两个括号,代价为 B
左边那个括号的权值,也就是 (())
,不包含你不喜欢的结构。
样例二
input
2 1 0 ()() 1 3
output
1
explanation
最优方案是直接使用操作 A
左边的那个括号的权值作为代价。
样例三
见附件下载。
数据范围与提示
保证
保证所有的权值在
测试点编号 | 特殊限制 |
---|---|
所有权值均相等 | |
无特殊限制 |
称一个字符串 (
和 )
组成,且对于 (
的数量均不少于 )
的数量。特别地,空串也是合法括号序列。
时间限制:
空间限制: