[LMXOI Round 1] Placer
题目背景
LMX 最近迷上了括号序列，她尤其钟爱合法括号序列。
LMX 为了检验 HQZ 的真诚，于是她出一道题准备考验下 HQZ。
题目描述
LMX 给出了一个长度为 $n$ 括号序列 $S$，以及一个长度为 $n$ 的序列 $a_i$。
定义 $w(l,r)=
\begin{cases}
a_r-a_l, & S_{l..r} \text{为合法括号序列}\\
\ 0 & \text{otherwise}
\end{cases}$
你可以将序列分成若干非空子段，定义整个序列的美丽度为每段的 $w(l , r)$ 之和。
求美丽度最大为多少。
输入输出格式
输入格式
第一行一个整数 $n$。
第二行一个字符串，代表括号序列。
第三行代表序列 $a$。
输出格式
第一行一个整数，表示最大的美丽度。
输入输出样例
输入样例 #1
5
()(()
1 3 2 3 5输出样例 #1
4输入样例 #2
10
()((())())
2 4 1 7 3 2 8 4 9 5输出样例 #2
8说明
**样例解释 #1**
原串可以划分成三个区间：$[1,2],[3,3],[4,5]$。贡献为 $(a_2-a_1)+0+(a_5-a_4)=(3-1)+0+(5-3)=4$
| 子任务编号 | $n$ | 特殊性质 | 分值 |
| :--------: | :--------: | :-------------: | :--: |
| Subtask #1 | $\le 5000$ | 无 | $30$ |
| Subtask #2 | $\le 10 ^ 5$ | 无 | $20$ |
| Subtask #3 | $\le 3 \times 10 ^ 6$ | 括号序列为 $()()\dots()$ | $15$ |
| Subtask #4 | $\le 3 \times 10 ^ 6$ | 无 | $35$ |
对于 $100\%$ 的数据，$1\le a_i \le 10^9$。