You have a length
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 | |
2 | 8 | All weights are equal |
3 | 12 | |
4 | 12 | |
5 | 16 | |
6 | 36 | - |
The first line contains 3 integers
The second line contains the bracket sequence.
The third line contains
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 |