Score: $400$ points

问题陈述

给定一个长度为 $2N$ 的字符串 $S$，由字符 ( 和 ) 组成。设 $S_i$ 表示 $S$ 中从左数第 $i$ 个字符。

你可以执行以下两种操作，每种操作可以执行零次或多次，且执行顺序任意：

• 选择一对整数 $(i,j)$，使得 $1\leq i < j \leq 2N$。交换 $S_i$ 和 $S_j$。此操作的成本为 $A$。

• 选择一个整数 $i$，使得 $1\leq i \leq 2N$。将 $S_i$ 替换为 ( 或 )。此操作的成本为 $B$。

你的目标是使 $S$ 成为一个正确的括号序列。找到实现此目标所需的最小总成本。可以证明，目标总是可以通过有限次操作实现。

什么是正确的括号序列？满足以下任一条件的字符串即为正确的括号序列：

• 它是一个空字符串。
• 它是由按照 (, $A$, ) 顺序连接而成的，其中 $A$ 是一个正确的括号序列。
• 它是由按照 $A$ 和 $B$ 顺序连接而成的，其中 $A$ 和 $B$ 都是正确的括号序列。

以上为大语言模型 kimi 翻译，仅供参考。

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