题目描述

给定一个由 $2N$ 个 ( 和 ) 组成的字符串 $S$。用 $S_i$ 表示 $S$ 从左起第 $i$ 个字符。

你可以按任意顺序、任意次数（包括 $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$ 按顺序连接得到的字符串。

输入格式

输入以如下格式从标准输入读入：

$N$ $A$ $B$ $S$

输出格式

请输出一行，表示所需总代价的最小值。

样例 1

输入

3 3 2
)))(()

输出

5

样例 2

输入

1 175 1000000000
()

输出

0

样例 3

输入

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

输出

52187538

说明/提示

限制条件

• 输入的所有数值均为整数。
• $1 \leq N \leq 5\times 10^5$
• $1 \leq A, B \leq 10^9$
• $S$ 是长度为 $2N$ 的、仅由 ( 和 ) 组成的字符串。

样例解释 1

操作的一种方案如下：

• 交换 $S_3$ 和 $S_4$，$S$ 变为 ))()()，代价为 $3$。
• 将 $S_1$ 替换为 (，$S$ 变为 ()()()，这是一个合法的括号序列，代价为 $2$。

本例中，将 $S$ 变为合法括号序列的总代价为 $5$。不存在总代价小于 $5$ 的方案。

样例解释 2

输入的 $S$ 已经是合法括号序列，无需进行任何操作。

由 ChatGPT 4.1 翻译