Maximizing Beauty in Parentheses Segmentation

You are given a parentheses sequence \(S\) of length \(n\) and a corresponding sequence \(\{a_i\}\) of length \(n\). You may partition the sequence into several non-empty contiguous segments. The beauty of a segment with boundaries \(l\) and \(r\) (0-indexed) is defined as follows:

[ w(l,r)=\begin{cases} a_r - a_l, & \text{if } S[l..r] \text{ is a valid parentheses sequence}\ 0, & \text{otherwise} \end{cases} ]

The beauty of the entire sequence is the sum of the beauties of all segments. Your task is to partition \(S\) in a way that maximizes its total beauty. Output the maximum beauty value possible.

inputFormat

The input consists of three lines:

1. The first line contains an integer \(n\) representing the length of the sequence.
2. The second line contains a string of \(n\) characters, each being either '(' or ')'.
3. The third line contains \(n\) space-separated integers, representing the sequence \(a_0, a_1, \ldots, a_{n-1}\).

outputFormat

Output a single integer, which is the maximum total beauty of the sequence.

sample

4
()()
1 2 3 4

3