Tommy has a balanced bracket sequence of length
, and a weight associated with each opening bracket.
Tommy desires to convert into a string that does not contain any sequence of the form
, where
and
are and hereinafter are any balanced bracket sequence. To do this, he can do two operations an arbitrary amount of times:
- Change the string from
to
, where
and
are and hereinafter are any (possibly unbalanced) bracket sequence. This incurs a cost of
times the weight of the first opening bracket plus
times the weight of the second opening bracket, where
and
are integers given in the input in
.
- Change the string from
to
. 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 into a string that does not contain any substring of the form
, where
and
are any balanced bracket sequence.
Constraints
Test | Other restrictions |
---|---|
1 - 3 | |
4 - 5 | All weights are equal. |
6 - 8 | |
9 - 12 | |
13 - 16 | |
17 - 25 | None. |
Input Specification
The first line contains three non-negative integers ,
, and
.
The second line contains a balanced bracket sequence of length
.
The third line contains positive integers
.
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 ,
,
, and
are all empty, incurring a cost of
.
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 .
Attachments
Attachments can be found here.
Comments