题目描述

一个长度为 $n$ 的合法括号序列，每对匹配括号可以不染色、染白色、染黑色，染白色和黑色分别有对应的代价，分别是 $a$ 和 $b$。相邻的非配对括号不能同色（都不染色也属于同色），问染色后的序列的最大代价。

序列的代价是每对配对括号的代价和。每对配对的括号必须染相同的颜色。

合法的括号序列是指由左括号 ( 和右括号 ) 组成的序列，满足以下条件：

1. 每个左括号都必须有对应的右括号，且右括号的位置必须在左括号之后。
2. 括号必须按照正确的嵌套关系闭合，即在任意位置，左括号的数量必须等于右括号的数量，并且左括号必须先闭合。

例如，以下序列是合法的括号序列：()、((()))、()()()、(()(()))；而以下序列是不合法的括号序列：

• (：没有对应的右括号。
• ())：右括号在左括号之前闭合。
• (()))：右括号数量多于左括号数量。

输入格式

第一行输入三个正整数 $n,a,b$。

第二行输入长度为 $n$ 的合法括号序列。

输出格式

输出一个数，表示染色后的序列的最大代价。

4 2 3
()()

5

6 2 3
((()))

8

数据范围/提示

对于所有测试点，$1≤ 𝑎,𝑏≤ 1000$。

• 对于测试点 $1$：$2≤ 𝑛≤ 10$。
• 对于测试点 $2\sim 5$：$2≤ 𝑛≤ 1000$。括号序列嵌套层数至多是 $1$，即 ()()()()...。
• 对于测试点 $6\sim 10$：$2≤ 𝑛≤1000$。