Background

LMX has recently become fascinated with bracket sequences, especially valid bracket sequences.

To test HQZ's sincerity, LMX has prepared a problem to challenge him.

Problem Description

LMX provides a bracket sequence \( S \) of length \( n \), and a sequence \( a_i \) of length \( n \).

Define ( w(l, r) = \begin{cases}
a_r - a_l, & \text{if } S_{l..r} \text{ is a valid bracket sequence} \
0 & \text{otherwise}
\end{cases} )

You can divide the sequence into several non-empty segments. The beauty of the entire sequence is defined as the sum of \( w(l, r) \) for each segment.

Find the maximum beauty.

Input Format

The first line contains an integer \( n \).

The second line contains a string representing the bracket sequence.

The third line represents the sequence \( a \).

Output Format

The first line contains an integer representing the maximum beauty.

Sample Input and Output

Sample Input #1

5
()(()
1 3 2 3 5

Sample Output #1

4

Sample Input #2

10
()((())())
2 4 1 7 3 2 8 4 9 5

Sample Output #2

8

Notes

Sample Explanation #1

The original sequence can be divided into three intervals: \([1,2]\), \([3,3]\), \([4,5]\). The contribution is \((a_2 - a_1) + 0 + (a_5 - a_4) = (3 - 1) + 0 + (5 - 3) = 4\).

For \(100\%\) of the data, \(1 \le a_i \le 10^9\).

见题面 Input 部分

见题面 Output 部分