B - Parenthesis Arrangement Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

長さ 2N の (, ) からなる文字列 S が与えられます．S の左から i 番目の文字を S_i と表します．

あなたは以下の 2 種類の操作を好きな順番で 0 回以上好きな回数行うことができます．

  • 1\leq i < j \leq 2N を満たす整数組 (i,j) を選ぶ．S_i と S_j を入れ替える．この操作にはコストが A かかる．

  • 1\leq i \leq 2N を満たす整数 i を選ぶ．S_i を ( または ) で置き換える．この操作にはコストが B かかる．

あなたの目標は S を正しい括弧列にすることです．目標を達成するために必要なコストの総和の最小値を求めてください．なお，有限回の操作で必ず目標を達成できることが証明できます．

正しい括弧列とは 正しい括弧列とは，以下のいずれかの条件を満たす文字列です．
  • 空文字列
  • ある正しい括弧列 A が存在して，(, A, ) をこの順に結合した文字列
  • ある空でない正しい括弧列 S,T が存在して，S,T をこの順に結合した文字列

制約

  • 入力される数値は全て整数
  • 1 \leq N \leq 5\times 10^5
  • 1\leq A,B\leq 10^9
  • S は長さ 2N の (, ) からなる文字列

入力

入力は以下の形式で標準入力から与えられる．

N A B
S

出力

答えを 1 行に出力せよ．

入力例 1

3 3 2
)))(()

出力例 1

5

操作の一例を示します．

  • S_3 と S_4 を入れ替える．S は ))()() となる．コストが 3 かかる．
  • S_1 を ( で置き換える．S は ()()() となり，これは正しい括弧列である．コストが 2 かかる．

この例では，S を正しい括弧列にするのにかかったコストの総和が 5 です．コストの総和が 5 未満で S を正しい括弧列にする操作方法は存在しません．

入力例 2

1 175 1000000000
()

出力例 2

0

入力の S は既に正しい括弧列なので，操作を行う必要はありません．

入力例 3

7 2622 26092458
))()((((()()((

出力例 3

52187538

Score: 400 points

Problem Statement

You are given a string S of length 2N consisting of the characters ( and ). Let S_i denote the i-th character from the left of S.

You can perform the following two types of operations zero or more times in any order:

  • Choose a pair of integers (i,j) such that 1\leq i < j \leq 2N. Swap S_i and S_j. The cost of this operation is A.

  • Choose an integer i such that 1\leq i \leq 2N. Replace S_i with ( or ). The cost of this operation is B.

Your goal is to make S a correct parenthesis sequence. Find the minimum total cost required to achieve this goal. It can be proved that the goal can always be achieved with a finite number of operations.

What is a correct parenthesis sequence? A correct parenthesis sequence is a string that satisfies any of the following conditions:
  • It is an empty string.
  • It is formed by concatenating (, A, ) in this order where A is a correct parenthesis sequence.
  • It is formed by concatenating A and B in this order where A and B are correct parenthesis sequences.

Constraints

  • All input values are integers.
  • 1 \leq N \leq 5\times 10^5
  • 1\leq A,B\leq 10^9
  • S is a string of length 2N consisting of the characters ( and ).

Input

The Input is given from Standard Input in the following format:

N A B
S

Output

Print the answer in a single line.

Sample Input 1

3 3 2
)))(()

Sample Output 1

5

Here is one way to operate:

  • Swap S_3 and S_4. S becomes ))()(). The cost is 3.
  • Replace S_1 with (. S becomes ()()(), which is a correct parentheses sequence. The cost is 2.

In this case, we have made S a correct bracket sequence for a total cost of 5. There is no way to make S a correct bracket sequence for less than 5.

Sample Input 2

1 175 1000000000
()

Sample Output 2

0

The given S is already a correct bracket sequence, so no operation is needed.

Sample Input 3

7 2622 26092458
))()((((()()((

Sample Output 3

52187538