{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eBaoBao has just found a strange sequence {\u0026lt;$s_1$, $v_1$\u0026gt;, \u0026lt;$s_2$, $v_2$\u0026gt;, $\\dots$, \u0026lt;$s_n$, $v_n$\u0026gt;} of length $n$ in his pocket. As you can see, each element \u0026lt;$s_i$, $v_i$\u0026gt; in the sequence is an ordered pair, where the first element $s_i$ in the pair is the left parenthesis \u0027(\u0027 or the right parenthesis \u0027)\u0027, and the second element $v_i$ in the pair is an integer.\u003c/p\u003e\n\n\u003cp\u003eAs BaoBao is bored, he decides to play with the sequence. At the beginning, BaoBao\u0027s score is set to 0. Each time BaoBao can select an integer $k$, swap the $k$-th element and the $(k+1)$-th element in the sequence, and increase his score by $(v_k \\times v_{k+1})$, if and only if $1 \\le k \u0026lt; n$, $s_k \u003d$ \u0027(\u0027 and $s_{k+1} \u003d$ \u0027)\u0027.\u003c/p\u003e\n\n\u003cp\u003eBaoBao is allowed to perform the swapping any number of times (including zero times). What\u0027s the maximum possible score BaoBao can get?\u003c/p\u003e\n\n\u003ch4\u003eInput\u003c/h4\u003e\n\u003cp\u003eThere are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:\u003c/p\u003e\n\n\u003cp\u003eThe first line contains an integer $n$ ($1 \\le n \\le 10^3$), indicating the length of the sequence.\u003c/p\u003e\n\n\u003cp\u003eThe second line contains a string $s$ ($|s| \u003d n$) consisting of \u0027(\u0027 and \u0027)\u0027. The $i$-th character in the string indicates $s_i$, of which the meaning is described above.\u003c/p\u003e\n\n\u003cp\u003eThe third line contains $n$ integers $v_1, v_2, \\dots, v_n$ ($-10^3 \\le v_i \\le 10^3$). Their meanings are described above.\u003c/p\u003e\n\n\u003cp\u003eIt\u0027s guaranteed that the sum of $n$ of all test cases will not exceed $10^4$.\u003c/p\u003e\n\n\u003ch4\u003eOutput\u003c/h4\u003e\n\u003cp\u003eFor each test case output one line containing one integer, indicating the maximum possible score BaoBao can get.\u003c/p\u003e\n\n\u003ch4\u003eSample\u003c/h4\u003e\n\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4\n6\n)())()\n1 3 5 -1 3 2\n6\n)())()\n1 3 5 -100 3 2\n3\n())\n1 -1 -1\n3\n())\n-1 -1 -1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e24\n21\n0\n2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\n\u003ch4\u003eHint\u003c/h4\u003e\n\u003cp\u003eFor the first sample test case, the optimal strategy is to select $k \u003d 2, 3, 5, 4$ in order.\u003c/p\u003e\n\n\u003cp\u003eFor the second sample test case, the optimal strategy is to select $k \u003d 2, 5$ in order.\u003c/p\u003e\n"}}]}