说明

一个仅由括号 ( 和 ) 组成的字符串被称为平衡的，如果它满足以下条件之一：

• 它是一个空字符串。
• 它是两个非空平衡字符串的连接。
• 对于某个平衡字符串 $a$，它是 (、$a$ 和 ) 的连接。

给定 $n$ 个括号字符 $s_1, \ldots, s_n$ 和 $n$ 个整数 $c_1, \ldots, c_n$。你需要选择零个或多个整数 $t_1, \ldots, t_k$，使得它们满足以下条件：

• $1 \leq t_1 < t_2 < t_3 < \cdots < t_k \leq n$。
• $s_{t_1}, s_{t_2}, \ldots, s_{t_k}$ 的连接是一个平衡字符串。

注意，如果你选择零个整数，上述条件总是满足。

你的任务是最大化 $\sum\limits_{i=1}^{k} c_{t_i}$。

输入格式

输入包含一个单独的测试用例，格式如下：

$$\begin{aligned} &n \\ &s_1 s_2 \cdots s_n \\ &c_1 \ c_2 \ \cdots \ c_n \end{aligned}$$

第一行包含一个整数 $n$（$1 \leq n \leq 300,000$）。第二行包含 $n$ 个字符 $s_1 s_2 \cdots s_n$，每个字符是 ( 或 )。第三行包含 $n$ 个整数 $c_1 \ c_2 \ \cdots \ c_n$（$|c_i| \leq 10^9$）。

输出格式

输出一行，表示通过选择零个或多个整数 $t_1, \ldots, t_k$ 所能得到的 $\sum\limits_{i=1}^{k} c_{t_i}$ 的最大可能值。

5
()(()
3 -9 -2 1 0

3

6
)()()(
-3 1 -4 1 -5 9

0

提示

翻译由 DeepSeek V3.2 完成