非常好的dp，可是我太菜做不出来。。
/*
第i个左括号不可能越过第i+1个左括号
如果第i个左括号到位置j，前提是第i+1个左括号就必须到位置j+1即以后
用dp[i][j]表示把第i个左括号转移到位置j的最大收益，
那么dp[i][j]=将i移到j位置的收益+max(dp[i+1][j+1..n])
这样的复杂度是n^3,一个n的复杂度用来重复计算max(dp[i+1][j+1..n])了
那么就额外开一个数组Max[i][j]：第i个括号转移到第j个位置之后的最大收益
*/
#include<bits/stdc++.h>
using namespace std;
#define maxn 1005
#define INF 0x3f3f3f3f
long long val[maxn],dp[maxn][maxn],n,num[maxn],pos[maxn],sum[maxn],t;
char s[maxn];
int main(){
cin>>t;
while(t--){
cin>>n;scanf("%s",s+);
for(int i=;i<=n;i++)cin>>val[i];
int l=,r=;//左括号右括号个数
for(int i=;i<=n;i++)
if(s[i]=='(')
pos[++l]=i,num[l]=r;
else
sum[++r]=sum[r-]+val[i]; memset(dp,,sizeof dp);
for(int i=l;i>=;i--){//第i个左括号
for(int j=n-(l-i);j>=pos[i];j--){
long long tmp=val[pos[i]]*(sum[num[i]+j-pos[i]]-sum[num[i]]);
dp[i][j]=dp[i+][j+]+tmp;
if(j<n-(l-i))dp[i][j]=max(dp[i][j],dp[i][j+]);//把第i个左括号移到位置j及以后的最大收益
}
for(int j=pos[i]-;j>=pos[i-];j--)dp[i][j]=dp[i][j+];
} long long ans=;
for(int i=;i<=n;i++)ans=max(ans,dp[][i]);
cout<<ans<<endl;
}
}