Background

LMX has recently become obsessed with bracket sequences, and she especially likes valid bracket sequences.

To test HQZ’s sincerity, LMX made a problem to challenge HQZ.

Problem Description

LMX gives 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, & S_{l..r} \text{ is a valid bracket sequence}\\ \ 0 & \text{otherwise} \end{cases}$

You can split the sequence into several non-empty subsegments. Define the beauty of the whole sequence as the sum of $w(l, r)$ over all segments.

Find the maximum possible beauty.

Input Format

The first line contains an integer $n$.

The second line contains a string representing the bracket sequence.

The third line contains the sequence $a$.

Output Format

The first line contains an integer, representing the maximum beauty.

5
()(()
1 3 2 3 5

4

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

8

Hint

Sample Explanation #1

The original string 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 testdata, $1 \le a_i \le 10^9$.

Translated by ChatGPT 5