题目背景

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$。

输出格式

第一行一个整数，表示最大的美丽度。

5
()(()
1 3 2 3 5

4

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

8

提示

样例解释 #1

原串可以划分成三个区间：$[1,2],[3,3],[4,5]$。贡献为 $(a_2-a_1)+0+(a_5-a_4)=(3-1)+0+(5-3)=4$

对于 $100\%$ 的数据，$1\le a_i \le 10^9$。