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.