P15726 [JAG 2023 Summer Camp #3] Best parentheses

一个仅由括号 `(` 和 `)` 组成的字符串被称为**平衡的**，如果它满足以下条件之一： - 它是一个空字符串。 - 它是两个非空平衡字符串的连接。 - 对于某个平衡字符串 $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}$ 的最大可能值。

翻译由 DeepSeek V3.2 完成