该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

一个长度为 $n$ 的合法括号序列，每对匹配括号可以不染色、染白色、染黑色。

染白色和黑色分别有对应的代价，分别是 $a$ 和 $b$。相邻的非配对括号不能同色（都不染色也属于同色），问染色后的序列的最大代价。

序列的代价是每对配对括号的代价和。

每对配对的括号必须染相同的颜色。

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

1. 每个左括号都必须有对应的右括号，且右括号的位置必须在左括号之后。

2. 括号必须按照正确的嵌套关系闭合，即在任意位置，左括号的数量必须等于右括号的数量，并且左括号必须先闭合。

例如，以下序列是合法的括号序列：

• ()
• ((()))
• ()()()
• (()(()))

而以下序列是不合法的括号序列：

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

输入格式

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

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

输出格式

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

4 2 3
()()

5

6 2 3
((()))

8

说明

【数据范围】

对于所有测试点，$1 \le a,b \le 1000$。

• 测试点 $1$，$2 \le n \le 10$；
• 测试点 $2-5$，$2 \le n \le 1000$。括号序列嵌套层数至多是 $1$，即 $()()()()...$；
• 测试点 $6-10$，$2 \le n \le 1000$，无特殊性质。