P8293 [NOI Qualifier Joint Contest 2022] Sequence Transformation

You have a valid bracket sequence $s$ of length $2 n$ in your hand. Each left parenthesis in $s$ has a weight. In your view, different bracket sequences bring different visual aesthetics. Therefore, you especially like bracket sequences with certain structures, and dislike bracket sequences with some other structures. You want to apply some transformations to $s$ to eliminate the structures you do not like. Specifically, you like structures of the form $\texttt{(A()B)}$ (where $\texttt{A}$ and $\texttt{B}$ are both valid bracket sequences; the same below), and you dislike structures of the form $\texttt{(A)(B)}$. You have two operations to change the positions among brackets. These two operations are: - Operation 1: In a string of the form $\texttt{p(A)(B)q}$, swap the two brackets between $\texttt{A}$ and $\texttt{B}$, transforming it into $\texttt{p(A()B)q}$ (where $\texttt{p}$ and $\texttt{q}$ are arbitrary strings and may be empty, but they are not necessarily valid bracket sequences respectively; the same below). Its cost is $x$ times the weight of the first left parenthesis in $\texttt{(A)}$ plus $y$ times the weight of the first left parenthesis in $\texttt{(B)}$, where $x, y \in \{0, 1\}$. - Operation 2: In a string of the form $\texttt{pABq}$, swap $\texttt{A}$ and $\texttt{B}$, transforming it into $\texttt{pBAq}$. This operation has no cost. Note: When swapping, all weights of left parentheses move together with their corresponding parentheses. Now you want to know: what is the minimum cost to transform $s$ into a bracket sequence that does not contain the structure you dislike?

The first line contains three integers $n, x, y$. The second line contains a valid bracket sequence of length $2n$, representing $s$. The third line contains $n$ positive integers, where the $i$-th one denotes the weight of the $i$-th left parenthesis from the left.

Output one integer in a single line, representing the minimum cost to transform $s$ into a bracket sequence that does not contain the structure you dislike.

**[Sample Explanation #1]** The optimal plan is to first use Operation 2 to swap the two pairs of parentheses, and then use Operation 1 (at this time $\texttt{A}$, $\texttt{B}$, $\texttt{p}$, and $\texttt{q}$ are all empty strings) to swap the two middle brackets. The cost is the weight of the bracket to the left of $\texttt{B}$, which is $1$. Finally, we obtain the bracket sequence $\texttt{(())}$, which does not contain the structure you dislike. **[Sample Explanation #2]** The optimal plan is to use Operation 1 directly, because the way to compute the cost is different this time: only the weight of the bracket to the left of $\texttt{A}$ is counted as the cost. **[Constraints]** It is guaranteed that $2 \le n \le 400000$ and $0 \le x, y \le 1$. It is guaranteed that all weights are within $[1, {10}^7]$. | Test Point ID | Special Constraints | |:-:|:-:| | $1 \sim 3$ | $n \leq 8$ | | $4 \sim 5$ | All weights are equal | | $6 \sim 8$ | $n \leq 20$ | | $9 \sim 12$ | $x = 0$，$y = 1$ | | $13 \sim 16$ | $n \le 2000$ | | $17 \sim 25$ | No special constraints | **[Hint]** A string $s$ is called a valid bracket sequence if and only if $s$ consists only of an equal number of characters $\texttt{(}$ and $\texttt{)}$, and for every prefix of $s$, the number of $\texttt{(}$ is at least the number of $\texttt{)}$. In particular, the empty string is also a valid bracket sequence. Translated by ChatGPT 5