Parenthesis Arrangement

时间限制：2s
空间限制：512MB

题目描述

给定一个长度为 $2N$ 的字符串 $S$，它只由 ( 和 ) 组成。你可以任意次、以任意顺序执行下列操作：选择 $1\le i<j\le 2N$ 并交换 $S_i,S_j$，代价为 $A$；或选择 $1\le i\le 2N$，将 $S_i$ 替换为 ( 或 )，代价为 $B$。

你需要将 $S$ 变为合法括号序列，求所需的最小总代价。合法括号序列可递归定义为空串、由某个合法括号序列 $T$ 构成的 (T)，或两个非空合法括号序列的连接。

输入格式

第一行包含三个整数 $N,A,B$。第二行包含字符串 $S$。

输出格式

输出一个整数，表示最小总代价。

样例输入 1

3 3 2
)))(()

样例输出 1

5

样例输入 2

1 175 1000000000
()

样例输出 2

0

样例输入 3

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

样例输出 3

52187538

数据范围

• $1\le N\le 5\times 10^5$。
• $1\le A,B\le 10^9$。
• $S$ 的长度为 $2N$，且只含 ( 和 )。