题目描述

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

输入格式

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

输出格式

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

样例输入1

4 2 3
()()

样例输出1

5

样例输入2

6 2 3
((()))

样例输出2

8

备注

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