题目描述

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$.

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

3

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

0