최적의 괄호

여는 괄호 (와 닫는 괄호 )로만 이루어진 문자열이 다음 조건 중 하나를 만족하면 균형 잡힌 문자열이라고 한다.

• 빈 문자열이다.
• 비어 있지 않은 균형 잡힌 문자열 두 개를 이어 붙인 것이다.
• 균형 잡힌 문자열 $a$에 대해 (, $a$, )를 순서대로 이어 붙인 것이다.

괄호 문자 $s_1, \dots, s_n$과 정수 $c_1, \dots, c_n$이 주어진다. 다음 조건을 만족하도록 0개 이상의 정수 $t_1, \dots, t_k$를 고른다.

• $1 \le t_1 < t_2 < \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 300\,000$)이 주어진다. 두 번째 줄에는 $n$개의 문자 $s_1 s_2 \cdots s_n$이 주어지며, 각 문자는 ( 또는 )이다. 세 번째 줄에는 $n$개의 정수 $c_1 c_2 \cdots c_n$ ($|c_i| \le 10^9$)이 주어진다.

$\sum_{i=1}^{k} c_{t_i}$의 최댓값을 한 줄에 출력한다.