Description

一个长度为n的合法括号序列， 每对匹配括号可以不染色、染白色、染黑色， 染白色和黑色 分别有对应的代价， 分别是a和b。相邻的非配对括号不能同色(都不染色也属于同色)， 问 染色后的序列的最大代价。 序列的代价是每对配对括号的代价和。 每对配对的括号必须染相同的颜色。 合法的括号序列是指由左括号"("和右括号")"组成的序列，满足以下条件：

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

• ()
• ((()))
• ()()()
• (()(())) 而以下序列是不合法的括号序列：
• (：没有对应的右括号。
• ())：右括号在左括号之前闭合。
• (()))：右括号数量多于左括号数量。

Input Format

第一行输入三个正整数 n, a, b。 第二行输入长度为 n 的合法括号序列。

Output Format

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

4 2 3
()()

5

6 2 3
((()))

8

Hint

对于所有测试点， 1 ≤ a, b ≤ 1000。 对于测试点 1： 2 ≤ n ≤ 10。 对于测试点2~5： 2 ≤ n ≤ 1000。括号序列嵌套层数至多是1，即()()()() …。 对于测试点6~ 10： 2 ≤ n ≤ 1000。