智乃的括号匹配
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

智乃现在有一个仅由"("和")"组成长度大小为N的字符串，字符串的每一个位置的字符都有自己的权值v_i和代价c_i。

智乃定义一对在该字符串中配对的括号对，假设左括号的坐标为i，右括号为j，该括号对的价值为两个括号权值的乘积v_i \cdot v_j。

"配对的括号"指从右往左开始对于每一个'('，从它开始向右找到第一个未配对的')'组成一对配对的括号。例如在"(())"中，假设下标分别为1,2,3,4首先找到2位置的'('与3的')'进行配对，接下来1位置的'('由于3已经配对，所以最终1和4配对

智乃定义整个字符串的价值为所有配对的括号对价值之和，注意并不要求整个字符串都是配对的。

现在对于任意下标为i的括号，智乃可以消耗它的代价c_i将其翻转，即"("变为")"，")"变为"("。

假设智乃的最总得分为经过若干次操作后，字符串的价值减去操作的代价之和，求智乃的最大得分。

注意当字符串价值小于操作的代价和时，智乃的得分可能是负数。

输入描述:

第一行输入一个正整数N(1\leq N \leq 500)表示字符串的大小。

接下来输入一个长度大小为N的字符串S(S_i\in \{'(',')'\})。

接下来输入N个正整数v_i(-10^{6}\leq v_i \leq 10^{6})表示字符串每个字符的权值。

接下来输入N个正整数c_i(1\leq c_i \leq 10^9)表示字符串每个字符的代价。

输出描述:

仅一行一个整数，表示最大得分。
示例1

输入

复制 
2
)(
4 3
10 10

输出

复制 
0

说明

如果将两个括号都翻转，则代价为20，收益为12，这样倒亏8，不如什么都不做。
示例2

输入

复制 
2
((
4 3
10 10

输出

复制 
2

说明

翻转第二个括号，则代价为10，收益为12，最大得分为2。
示例3

输入

复制 
4
()()
-1 100 10 10
1000 101 100 100

输出

复制 
789

说明

最优操作位变成"(())"。得分990，代价为201。
示例4

输入

复制 
2
()
-1 100
10 10

输出

复制 
-10

说明

如果放着不动，会直接亏100，不如翻转一下主动亏10