[省选联考 2022] 序列变换

题目描述

你手里有一个长度为 $2 n$ 的合法括号序列 $s$。$s$ 的每一个左括号有一个权值。 在你眼中,不同的括号序列带来的视觉美感不尽相同。因此,你对具有某一种结构的括号序列特别喜欢,而讨厌具有其他一些结构的括号序列。你希望对 $s$ 进行一些变换,以消除掉一些自己不喜欢的结构。 具体而言,形如 $\texttt{(A()B)}$(其中 $\texttt{A}$、$\texttt{B}$ 均为合法括号序列,下同)的结构是你喜欢的, 而形如 $\texttt{(A)(B)}$ 的结构是你不喜欢的。你有两种操作来改变括号之间的位置。 这两种操作如下: - 操作 1:交换形如 $\texttt{p(A)(B)q}$ 的串中 $\texttt{A}$ 和 $\texttt{B}$ 之间的两个括号,变换为 $\texttt{p(A()B)q}$(其中 $\texttt{p}$、$\texttt{q}$ 为任意串,可以为空,但不一定分别为合法括号序列,下同),它的代价为 $x$ 乘 $\texttt{(A)}$ 中第一个左括号的权值加上 $y$ 乘 $\texttt{(B)}$ 中第一个左括号的权值,其中 $x, y \in \{0, 1\}$; - 操作 2:交换形如 $\texttt{pABq}$ 的串中的 $\texttt{A}$ 和 $\texttt{B}$,变换为 $\texttt{pBAq}$,这个操作不需要代价。 注意:交换的时候所有左括号的权值是跟着这个括号一起交换的。 你现在想知道的是,将 $s$ 变换为一个不包含你不喜欢的结构的括号序列至少需要多少代价?

输入输出格式

输入格式


第一行三个整数 $n, x, y$。 第二行一个长度为 $2n$ 的合法括号序列,表示 $s$。 第三行 $n$ 个正整数,其中第 $i$ 个表示左数第 $i$ 个左括号的权值。

输出格式


一行一个整数,表示把 $s$ 变换为一个不包含你不喜欢的结构的括号序列至少需要的代价。

输入输出样例

输入样例 #1

2 0 1
()()
1 3

输出样例 #1

1

输入样例 #2

2 1 0
()()
1 3

输出样例 #2

1

输入样例 #3

见附件中的 bracket/bracket3.in

输出样例 #3

见附件中的 bracket/bracket3.ans

说明

**【样例解释 #1】** 最优方案是先使用操作 2 交换两对括号,然后使用操作 1(此时 $\texttt{A}$、$\texttt{B}$、$\texttt{p}$、$\texttt{q}$ 都是空串)交换中间的两个括号,代价为 $\texttt{B}$ 左边那个括号的权值,也就是 $1$。最后得到括号序列 $\texttt{(())}$,不包含你不喜欢的结构。 **【样例解释 #2】** 最优方案是直接使用操作 1,因为此时计算代价的方式不同了,这次只算 $\texttt{A}$ 左边的那个括号的权值作为代价。 **【数据范围】** 保证 $2 \le n \le 400000$,$0 \le x, y \le 1$。 保证所有的权值在 $[1, {10}^7]$ 之内。 | 测试点编号 | 特殊限制 | |:-:|:-:| | $1 \sim 3$ | $n \leq 8$ | | $4 \sim 5$ | 所有权值均相等 | | $6 \sim 8$ | $n \leq 20$ | | $9 \sim 12$ | $x = 0$,$y = 1$ | | $13 \sim 16$ | $n \le 2000$ | | $17 \sim 25$ | 无特殊限制 | **【提示】** 称一个字符串 $s$ 为合法括号序列,当且仅当 $s$ 仅由数量相等的字符 $\texttt{(}$ 和 $\texttt{)}$ 组成,且对于 $s$ 的每一个前缀而言,其中 $\texttt{(}$ 的数量均不少于 $\texttt{)}$ 的数量。特别地,空串也是合法括号序列。