Tommy has a balanced bracket sequence $s$ of length $2n$, and a weight associated with each opening bracket.

Tommy desires to convert $s$ into a string that does not contain any sequence of the form $(A)(B)$, where $A$ and $B$ are and hereinafter are any balanced bracket sequence. To do this, he can do two operations an arbitrary amount of times:

1. Change the string from $p(A)(B)q$ to $p(A()B)q$, where $p$ and $q$ are and hereinafter are any (possibly unbalanced) bracket sequence. This incurs a cost of $x$ times the weight of the first opening bracket plus $y$ times the weight of the second opening bracket, where $x$ and $y$ are integers given in the input in $\{0,1\}$.
2. Change the string from $pABq$ to $pBAq$. This incurs no cost. Note that the weights of the opening brackets are changed as they are moved around.

Find the minimum possible cost incurred to convert $s$ into a string that does not contain any substring of the form $(A)(B)$, where $A$ and $B$ are any balanced bracket sequence.

Constraints

$2\le n\le 4\times {10}^5$

$0\le x,y\le 1$

$1\le w_i\le {10}^7$

Test	Other restrictions
1 - 3	$n\le 8$
4 - 5	All weights are equal.
6 - 8	$n\le 20$
9 - 12	$x=0$, $y=1$
13 - 16	$n\le 2000$
17 - 25	None.

Input Specification

The first line contains three non-negative integers $n$, $x$, and $y$.

The second line contains a balanced bracket sequence $s$ of length $2n$.

The third line contains $n$ positive integers $w_1,w_2,\dots ,w_n$.

Output Specification

Output the answer.

Sample Input 1

2 0 1
()()
1 3

Sample Output 1

1

Sample Explanation 1

The optimal solution is to first use operation 2 to exchange the first and second pair of parentheses. Then, use operation 1 to exchange the inner pair of parentheses, where $A$, $B$, $p$, and $q$ are all empty, incurring a cost of $3\times 0+1\times 1=1$.

Sample Input 2

2 1 0
()()
1 3

Sample Output 2

1

Sample Explanation 2

We may use operation 1 directly, incurring a cost of $1\times 1+3\times 0=1$.

Attachments

Attachments can be found here.