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

• 它是空字符串。
• 它是两个非空平衡字符串的拼接。
• 它是 "("、一个平衡字符串 $a$ 和 ")" 的拼接。

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

• $1 \le t_1 < t_2 < t_3 < \dots < t_k \le n$。
• $s_{t_1}, s_{t_2}, \dots, s_{t_k}$ 的拼接是一个平衡字符串。

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

你的任务是找到 $\sum_{i=1}^k c_{t_i}$ 的最大可能值。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 3 \cdot 10^5$)。 第二行包含 $n$ 个字符 $s_1s_2 \dots s_n$，每个字符要么是 "(" 要么是 ")"，中间没有空格。 第三行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$ ($|c_i| \le 10^9$)。

输出格式

输出一行，包含一个整数：选择零个或多个整数 $t_1, \dots, t_k$ 后，$\sum_{i=1}^k c_{t_i}$ 的最大可能值。

样例

样例输入 1

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

样例输出 1

3

样例输入 2

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

样例输出 2

0