说明

给一个由小括号组成的序列和 $n$ 个括号串，要你在序列中匹配允许不连续的子串。

母序列的每个括号最多被匹配一次。

一种可能的不连续子串匹配方式为 )()( 中匹配 ))( 。

每个括号串有一个值 $v$，代表对这个串每匹配一个括号得到的价值。

每个括号串均可以多次匹配，可以随时停止匹配，但是不能在未匹配完一个括号串的情况下开始匹配其他括号串。

注意如果你跳过了母序列的某几个括号去匹配后面的，那么你将不能返回前面继续进行匹配。

求匹配能得到的最大值。

输入格式

第一行一个整数 $n$，表示括号串的个数。

第二行一个字符串 $k$，表示给出的母序列。

接下来 $n$ 行，每行一个括号串 $a$ 和一个数字 $v$。在这 $n$ 行中，第 $i$ 行的字符 $a_i,v_i$ 表示一个存在的括号串以及匹配这个括号串内一个括号所能得到的价值。

输出格式

一个数 $r$，表示能取得的最大值。

3 
((()())(()
(() 4
() 2
()()() 5

32

3
())()))()
()) 9
()() 8
())) 7

73

提示

【温馨提示】

为了卡掉错解开大了数据范围，请注意常数因子对程序产生的影响。

【数据范围】

本题使用捆绑测试。

对于 $100\%$ 的数据， $1 \le n \le 500, 1 \le len(k) \le 10^4, 1 \le len(a) \le 300,0 \le v \le 10^3$。

【样例 $1$ 解释】

最佳方案为先匹配 (() ，后匹配 ()()() （ 注意最多只能匹配到 ()() ），答案为 $4\times3 + 5 \times 4 = 32$。

一种可行的匹配方法为方括号括起来的部分 (【(()()】)(【()】 。

而若先匹配 (() ，再匹配 () ，最后匹配 (() 的价值为 $4\times 3 + 2\times 2 + 4\times 3 = 28$，并非最佳方案。

注意我们不能先匹配 (() ，再匹配 ()()() 中一个括号，最后匹配 (() ，因为我们可以随时停止匹配，但不能在未匹配完某个串的情况下开始匹配另一个串。

【样例 $2$ 解释】

最佳方案先匹配 ())，再匹配 ())) 最后匹配 ()) （ 注意最多只能匹配到 () ）, 答案为 $9\times 3 + 7 \times 4 + 9 \times 2 = 73$。