BaoBao 在他的口袋里发现了一个奇怪的序列 $\{, , \dots, \}$，其长度为 $n$。 如你所见，序列中的每个元素 $$ 都是一个有序对，其中第一个元素 $s_i$ 是左括号 '(' 或右括号 ')'，第二个元素 $v_i$ 是一个整数。

由于 BaoBao 很无聊，他决定玩弄这个序列。起初，BaoBao 的分数为 $0$。每次 BaoBao 可以选择一个整数 $k$，交换序列中第 $k$ 个元素和第 $k+1$ 个元素，并将他的分数增加 $(v_k \times v_{k+1})$，当且仅当 $1 \le k < n$，$s_k = \text{'('}$ 且 $s_{k+1} = \text{')'}$。

BaoBao 可以进行任意次数的交换（包括零次）。BaoBao 能得到的最大分数是多少？

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含一个整数 $n$ ($1 \le n \le 10^3$)，表示序列的长度。 第二行包含一个长度为 $n$ 的字符串 $s$，由 '(' 和 ')' 组成。字符串中的第 $i$ 个字符表示 $s_i$，其含义如上所述。 第三行包含 $n$ 个整数 $v_1, v_2, \dots, v_n$ ($-10^3 \le v_i \le 10^3$)。其含义如上所述。

保证所有测试数据的 $n$ 之和不超过 $10^4$。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示 BaoBao 能得到的最大分数。

样例

输入 1

4
6
)())()
1 3 5 -1 3 2
6
)())()
1 3 5 -100 3 2
3
())
1 -1 -1
3
())
-1 -1 -1

输出 1

24
21
0
2

说明

对于第一个样例，最优策略是依次选择 $k = 2, 3, 5, 4$。 对于第二个样例，最优策略是依次选择 $k = 2, 5$。