AT_arc175_b [ARC175B] Parenthesis Arrangement

给定一个由 $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 \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 翻译