seqtransform

Sequence Transformation

You have a length 2n nice bracket sequence S. Each left parenthesis has a weight. Namely the ith left parenthesis has weight wi

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 xw+yu where x,y{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

1n400000
0x,y1
1wi107

Subtasks # Score Constraits
1 12 n8
2 8 All weights are equal
3 12 n20
4 12 x=0,y=1
5 16 n2000
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 ith integer is wi

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


Submitting to 'seqtransform'


You're not logged in! Click here to login


Submitting to 'seqtransform'


You're not logged in! Click here to login


Submitting .cpp to 'seqtransform'


You're not logged in! Click here to login

Time Limit: 10 Seconds
Memory Limit: 1024MB
Your best score: 0
Source: LOJ #3704

Subtask Score
1 12
2 8
3 12
4 12
5 20
6 36