영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
(그림은 원문 저장소에서 볼 수 있습니다)
Lulli, The Cat
Louise loves her cat Lulli very much and therefore plants lots of catnip.
Now Louise wants to create a beautiful necklace for Lulli with N charms placed in a ring. On each charm there is exactly one symbol, either ( or ). The necklace also has a bell that marks where to start reading.
To make the necklace extra beautiful, Louise wants the necklace to be balanced. For help, Louise hires a jeweler who can modify the necklace. As payment, she uses catmints.
The jeweler can remove any charm for a cost of a catmints per charm. The jeweler can also rotate the necklace one step, so that the first charm moves to the end, which costs b catmints. Louise is also satisfied if the necklace becomes completely empty, but then she must pay to remove each charm.
Louise therefore wants to make the necklace balanced at the lowest possible cost.
A necklace is balanced if its symbols, read in order from the bell, form a balanced parenthesis string. A parenthesis string is balanced if:
- It is empty, or
- It can be written as AB, where both A and B are balanced strings, or
- It can be written as (A), where A is a balanced string.
Input
The first line contains three integers N, a and b (1 ≤ N ≤ 5 · 10^5, 0 ≤ a,b ≤ 10^9).
The second line contains a string s of length N. Each symbol in s is either ( or ).
Output
Print one integer: the minimum possible total cost to make the necklace balanced.
Scoring
Your solution will be tested on a set of test groups. To earn points for a group, you must pass all test cases in that group.
| Group | Points | Constraints |
|---|---|---|
| 1 | 11 | a = 1, b = 10^9 |
| 2 | 16 | N ≤ 15 |
| 3 | 19 | N ≤ 100 |
| 4 | 21 | N ≤ 2000 |
| 5 | 9 | b = 0 |
| 6 | 8 | a = 10^9, b = 1, there are equally many ( as ) in the input string. |
| 7 | 16 | No additional constraints. |
Explanation of Samples
In sample 1, you can first rotate the necklace two steps.
(그림은 원문 저장소에서 볼 수 있습니다)
Then the necklace reads as )(()).
(그림은 원문 저장소에서 볼 수 있습니다)
If you then remove the first charm, which is ), the necklace reads as (()), which is balanced.
(그림은 원문 저장소에서 볼 수 있습니다)
The total cost is 3 + 3 + 2 = 8 catmints.
In sample 2, you can remove the second charm, which is ), and then the last charm, which is (. Then the necklace reads as ()()(), which is balanced. The total cost is 4 + 4 = 8 catmints.
In sample 3, you can rotate the necklace three steps, so that the necklace reads as ()()(()). It is already balanced, so the total cost is 3 + 3 + 3 = 9 catmints.
예제
예제 1
5 2 3 )))((
8
예제 2
8 4 3 ())()()(
8
예제 3
8 5 3 ())()()(
9