seqtransform

Sequence Transformation

You have a length \(2n\) nice bracket sequence \(S\). Each left parenthesis has a weight. Namely the \(i^{th}\) left parenthesis has weight \(w_i\)

Nice bracket sequences are bracket sequences that are not ugly.
An ugly sequence is a sequence that can take the form of q(A)(B)p where A, B are valid bracket sequences (possibly empty) while p, q are strings (possibly empty). You are provided two operations to transform the bracket sequence

The two operations are as follows:

• Operation 1:
  Transform the sequence of form q(A)(B)p to q(A( )B)p where A, B are valid bracket sequences (possibly empty) while p, q are strings (possibly empty).
  Let the weight of the first and second parentheses be \(w, u\) respectively.
  The cost of this operation is \(x*w+y*u \) where \(x, y \in \{0, 1\}\)
• Operation 2:
  Transform the sequence of form qABp to qBAp where A, B are valid bracket sequences (possibly empty) while p, q are strings (possibly empty).
  This operation has no cost

Note: When transforming the sequence, the weights of the left parentheses are transformed accordingly as well. In the case of operation 1, the first parenthesis pair will be transformed to the outer pair (q(A)[B]p to q(A[ ]B)p)

Find the minimum cost required to transform \(S\) to a nice bracket sequence.

Limits

\(1 \leq n \leq 400000\)
\(0\leq x, y \leq 1\)
\(1 \leq w_i \leq 10^7\)

Subtasks #	Score	Constraits
1	12	\(n \leq 8\)
2	8	All weights are equal
3	12	\(n \leq 20\)
4	12	\(x = 0, y = 1\)
5	16	\(n \leq 2000\)
6	36	-

Input format

The first line contains 3 integers \(n, x, y\).
The second line contains the bracket sequence.
The third line contains \(n\) integers where the \(i^{th}\) integer is \(w_i\)

Output format

Output a single integer, the minimum cost needed to transform the bracket sequence to a nice bracket sequence.

Samples

Sample Input 1	Sample Output 1
2 0 1 ()() 1 3	1
Sample Input 2	Sample Output 2
2 1 0 ()() 1 3	1