{"trustable":false,"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":"\t\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n\t MathJax.Hub.Config({\n\t extensions: [\"tex2jax.js\"],\n\t jax: [\"input/TeX\", \"output/SVG\"],\n\t tex2jax: {\n\t inlineMath: [ [\u0027$\u0027,\u0027$\u0027], [\"\\\\(\",\"\\\\)\"] ],\n\t displayMath: [ [\u0027$$\u0027,\u0027$$\u0027], [\"\\\\[\",\"\\\\]\"] ],\n\t processEscapes: true\n\t },\n\t });\n\t\u003c/script\u003e\n\t\u003cscript type\u003d\"text/javascript\"\n\t src\u003d\"https://cdn.staticfile.org/mathjax/2.7.0/MathJax.js\"\u003e\n\t\u003c/script\u003e\n \u003cp\u003e题目翻译,给你一堆括号,第i个括号的权值是ai,现在当相邻的括号是“()”这样一左一右匹配的时候,可以让这2个括号交换位置变成“)(”然后产生ai * aj点权值的贡献,可以交换任意次,现在问最大会产生多少总贡献,注意,括号交换后,他们对应的权值仍然是不变的,也就是说不是位置对应权值,而是括号对应权值\u003cp\u003e\n \u003cp\u003e例如( ) ) 然后权值是1 2 3,先1号和2号括号匹配交换,产生2点权值,变成) ( ),此时权值变成2 1 3,然后2号括号和3号括号交换,产生3点权值变成) ) (,一共产生5点权值\u003c/p\u003e\n \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 \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 \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 "}},{"title":"Input","value":{"format":"HTML","content":"\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 \u003cp\u003eThe first line contains an integer $n$ ($1 \\le n \\le 10^3$), indicating the length of the sequence.\u003c/p\u003e \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 \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 \u003cp\u003eIt\u0027s guaranteed that the sum of $n$ of all test cases will not exceed $10^4$.\u003c/p\u003e \n \u003ch4"}},{"title":"Output","value":{"format":"HTML","content":"\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 \u003ch4"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003c/h4\u003e \n \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 \n \u003ch4"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003c/h4\u003e \n \u003cpre\u003e24\n21\n0\n2\n\u003c/pre\u003e \n \u003ch4"}},{"title":"Hint","value":{"format":"HTML","content":"\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 \u003cp\u003eFor the second sample test case, the optimal strategy is to select $k \u003d 2, 5$ in order.\u003c/p\u003e \n "}}]}