P15726 [JAG 2023 Summer Camp #3] Best parentheses

A string consisting only of parentheses ‘(’ and ‘)’ is called **balanced** if it satisfies one of the following conditions. - It is an empty string. - It is a concatenation of two non-empty balanced strings. - It is a concatenation of ‘(’, $a$, and ‘)’, for some balanced string $a$. You are given $n$ characters $s_1, \ldots, s_n$ of parentheses and $n$ integers $c_1, \ldots, c_n$. Then, you have to choose zero or more integers $t_1, \ldots, t_k$ so that they satisfy the following conditions. - $1 \leq t_1 < t_2 < t_3 < \cdots < t_k \leq n$. - The concatenation of $s_{t_1}, s_{t_2}, \ldots, s_{t_k}$ is a balanced string. Note that the above conditions are always satisfied if you choose zero integers. Your task is to maximize $\sum_{i=1}^{k} c_{t_i}$.

The input consists of a single test case of the following format. $$ \begin{aligned} &n \\ &s_1 s_2 \cdots s_n \\ &c_1 \ c_2 \ \cdots \ c_n \end{aligned} $$ The first line consists of an integer $n$ ($1 \leq n \leq 300,000$). The second line consists of $n$ characters $s_1 s_2 \cdots s_n$, each of which is either ‘(‘ or ‘)’. The third line consists of $n$ integers $c_1 \ c_2 \ \cdots \ c_n$ ($|c_i| \leq 10^9$).

Output in a line the maximum possible value of $\sum_{i=1}^{k} c_{t_i}$ by choosing zero or more integers $t_1, \ldots, t_k$.