Problem Description

You have a valid parentheses sequence \( s \) of length \( 2n \). Each left parenthesis in \( s \) has an associated weight.

In your view, different parentheses sequences have varying degrees of visual appeal. You particularly like sequences with certain structures and dislike others. You wish to transform \( s \) to eliminate the structures you dislike.

Specifically, structures like \(\texttt{(A()B)}\) (where \(\texttt{A}\) and \(\texttt{B}\) are valid parentheses sequences) are liked, while structures like \(\texttt{(A)(B)}\) are disliked. You have two operations to rearrange the parentheses:

• Operation 1: Swap the two parentheses between \(\texttt{A}\) and \(\texttt{B}\) in a string like \(\texttt{p(A)(B)q}\), transforming it to \(\texttt{p(A()B)q}\) (where \(\texttt{p}\) and \(\texttt{q}\) are arbitrary strings, possibly empty, but not necessarily valid parentheses sequences). The 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: Swap \(\texttt{A}\) and \(\texttt{B}\) in a string like \(\texttt{pABq}\), transforming it to \(\texttt{pBAq}\). This operation has no cost.

Note: When swapping, the weights of the left parentheses move with them.

You want to know the minimum cost required to transform \( s \) into a sequence that does not contain any disliked structures.

Input Format

The first line contains three integers \( n \), \( x \), and \( y \).

The second line contains a valid parentheses sequence \( s \) of length \( 2n \).

The third line contains \( n \) positive integers, where the \( i \)-th integer represents the weight of the \( i \)-th left parenthesis from the left.

Output Format

Output a single integer, the minimum cost required to transform \( s \) into a sequence without any disliked structures.

Sample Input and Output

Sample Input #1

2 0 1
()()
1 3

Sample Output #1

1

Sample Input #2

2 1 0
()()
1 3

Sample Output #2

1

Sample Input #3

See attached file bracket/bracket3.in

Sample Output #3

See attached file bracket/bracket3.ans

Notes/Hints

[Sample Explanation #1]

The optimal solution is to first use Operation 2 to swap the pairs of parentheses, then use Operation 1 (where \(\texttt{A}\), \(\texttt{B}\), \(\texttt{p}\), and \(\texttt{q}\) are empty strings) to swap the middle two parentheses. The cost is the weight of the left parenthesis in \(\texttt{B}\), which is \( 1 \). The resulting sequence is \(\texttt{(())}\), which does not contain any disliked structures.

[Sample Explanation #2]

The optimal solution is to directly use Operation 1, as the cost calculation method is different now, only considering the weight of the left parenthesis to the left of \(\texttt{A}\).

[Data Range]

It is guaranteed that \( 2 \le n \le 400000 \) and \( 0 \le x, y \le 1 \).

All weights are within the range \([1, 10^7]\).

[Hint]

A string \( s \) is considered a valid parentheses sequence if and only if \( s \) consists of equal numbers of characters \(\texttt{(}\) and \(\texttt{)}\), and for every prefix of \( s \), the number of \(\texttt{(}\) is not less than the number of \(\texttt{)}\). Notably, an empty string is also a valid parentheses sequence.

见题面 Input 部分

见题面 Output 部分