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