You have a valid bracket sequence $s$ of length $2n$. Each left parenthesis in $s$ has a weight.

In your view, different bracket sequences have different visual aesthetics. Therefore, you particularly like bracket sequences with a certain structure and dislike those with other structures. You wish to perform some transformations on $s$ to eliminate the structures you dislike.

Specifically, a structure of the form $(A()B)$ (where $A$ and $B$ are both valid bracket sequences, same below) is one you like, while a structure of the form $(A)(B)$ is one you dislike. You have two operations to change the positions of the parentheses.

These two operations are as follows: Operation 1: Swap two parentheses between $A$ and $B$ in a string of the form $p(A)(B)q$, transforming it into $p(A()B)q$ (where $p, q$ are arbitrary strings, which may be empty, and are not necessarily valid bracket sequences, same below). The cost of this operation is $x$ multiplied by the weight of the first left parenthesis in $(A)$ plus $y$ multiplied by the weight of the first left parenthesis in $(B)$, where $x, y \in \{0, 1\}$. Operation 2: Swap $A$ and $B$ in a string of the form $pABq$, transforming it into $pBAq$. This operation has no cost.

Note: When swapping, the weights of all left parentheses are swapped along with the parentheses themselves.

You now want to know the minimum cost required to transform $s$ into a bracket sequence that does not contain any of the structures you dislike.

Input

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 integer represents the weight of the $i$-th left parenthesis from the left.

Output

A single integer representing the minimum cost required to transform $s$ into a bracket sequence that does not contain any of the structures you dislike.

Examples

Input 1

1 0 1
()()
1 3

Output 1

1

Note 1

The optimal strategy is to first use Operation 2 to swap the two pairs of parentheses, and then use Operation 1 (at this point $A, B, p, q$ are all empty strings) to swap the two middle parentheses, with a cost equal to the weight of the parenthesis to the left of $B$, which is $1$. Finally, we obtain the bracket sequence $(())$, which does not contain the structure you dislike.

Input 2

1 1 0
()()
1 3

Output 2

1

Note 2

The optimal strategy is to use Operation 1 directly, because the way the cost is calculated is different here; this time, only the weight of the parenthesis to the left of $A$ is counted as the cost.

Input 3

See bracket/bracket3.in and bracket/bracket3.ans in the contestant directory.

Subtasks

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]$.

Note

A string $s$ is called a valid bracket sequence if and only if $s$ consists only of an equal number of '(' and ')' characters, and for every prefix of $s$, the number of '(' is not less than the number of ')'. In particular, the empty string is also a valid bracket sequence.