30374번 - 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, \dots , s_n$ of parentheses and $n$ integers $c_1, \dots , c_n$. Then, you have to choose zero or more integers $t_1, \dots ,t_k$ so that they satisfy the following conditions.

• 1ドル \le t_1 < t_2 < t_3 < \dots < t_k \le n$.
• The concatenation of $s_{t_1}, s_{t_2}, \dots , 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.

$n$

$s_1 s_2 \cdots s_n$

$c_1$ $c_2$ $\cdots$ $c_n$

The first line consists of an integer $n$ (1ドル \le n \le 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| \le 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, \dots ,t_k$.

제한

힌트