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:
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   
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 a single integer, the minimum cost needed to transform the bracket sequence to a nice bracket sequence.
Sample Input 1  Sample Output 1 
2 0 1

1

Sample Input 2  Sample Output 2 
2 1 0

1

Subtask  Score 

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