题目描述

郭老师是乔斯花花幼儿园 的一个大班老师，他知道同学们括号匹配学的很好，于是他给同学们出了一道经典的括号匹配题

首先来解释一下什么是括号匹配

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

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

而以下序列是不合法的括号序列（只是举个例子）：

• (：左小括号右边没有右小括号
• ()))：最后面的小括号匹配不了
• (()))：括号数量不匹配

这是deepseek的解释

如果你依旧没没懂，那肯定是deepseek的锅，和出题人无关

当然只是括号匹配太简单了，郭老师决定加大难度，他决定用自己染料来给他们染色，一个长度为 m 的合法括号序列，每对匹配括号可以不染色、染金色、染银色，染金色和银色分别有对应的花费，金色的花费是 a ,银色的花费是 b。相邻的非配对括号不能同色（如果不染色的话属于同一个颜色,然后金色不一定比银色贵），郭老师希望染色便宜点，但是幼儿园的强哥想捣蛋，故意想贵的，于是把最小花费改成了最大花费。

所以本题是问你整个序列合理染色的最大花费，整个序列的是每对配对括号的花费和。每对配对的括号必须染相同的颜色。

输入格式

第一行输入三个正整数 n,a,b，分别代表序列的长度，染金色的价格，染银色的价格

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

输出格式

整个序列合理染色的最大花费，整个序列的是每对配对括号的花费和。每对配对的括号必须染相同的颜色。

4 2 3
()()

10

提示

对于所有测试点，$1≤a,b,n≤1000$。

• 对于10%的数据，$2≤n≤10$,如果你是搜索高手，大概率10分
• 对于另外40%的数据,括号序列嵌套层数至多是1，即()()()()⋯这种样子