题目描述

给定一个长为 $n$ 的括号串，其中有一些是 ?。给定常数 $a,b$。你要取出其中若干不交的子段，使得每一段都存在把 ? 换成括号的方法使之成为合法括号串。长度为 $i$ 的段的收益 $ai+b$，一个方案的收益是所有段的收益和。求最大的收益。

输入格式

第一行输入三个整数 $n$，$a$ 和 $b$。第二行输入给定括号串。

输出格式

输出一行，包含一个整数，表示答案。

样例数据

样例 1 输入

10 -406834 918906
?)?)(?((()

样例 1 输出

420952

样例 2

见下发文件 ex_bracket2.in 和 ex_bracket2.out，该测试用例满足子任务 2 的约束条件。

样例 3

见下发文件 ex_bracket3.in 和 ex_bracket3.out，该测试用例满足子任务 3 的约束条件。

样例 4

见下发文件 ex_bracket4.in 和 ex_bracket4.out，该测试用例满足子任务 4 的约束条件。

样例 5

见下发文件 ex_bracket5.in 和 ex_bracket5.out。

数据规模与约定

全部数据均保证 $1\le n\le 5\times 10^5$ ，$|a|,|b|\le 10^6$ ，输入的字符串只包含 ()? 三 种字符。 本题采用子任务捆绑测试，各个子任务详细信息如下：