#include <bits/stdc++.h>

using namespace std;

#define pb push_back

#define fi first

#define se second

typedef long long ll;

typedef pair<int, int> pii;

const int inf = 0x3f3f3f3f;

const int maxn = 1e3+;

char str[maxn];

ll dp[maxn],mul[maxn],a[maxn];

int main(){

            int T;  scanf("%d", &T);

            while(T--) {

                int n;  scanf("%d", &n);

                scanf("%s", str+);

                for(int i=; i<=n; i++) scanf("%lld", &a[i]);

                for(int i=; i<=n; i++) dp[i] = ;

                ll ans = ;

                for(int i=n; i>=; i--) {

                    if(str[i] == '(') {

                        ll sum = ;

                        for(int j=;   j<=n; j++) mul[j] = ;

                        for(int j=i; j<=n; j++) {

                            if(str[j] == ')')sum += a[i] * a[j];

                            mul[j] = sum;

                        }

                        ll mx = -2e18;

                        for(int j=n; j>; j--) {

                            mx = max(mx, dp[j]);

                            dp[j] = mx + mul[j];

                            ans = max(ans, dp[j]);

                        }

                    }

                }

                printf("%lld\n", ans);

            }

            return ;

}