{"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刚刚在口袋里找到了一个奇怪的序列{\u0026lt;$s_1$, $v_1$\u0026gt;, \u0026lt;$s_2$, $v_2$\u0026gt;, $\\dots$, \u0026lt;$s_n$, $v_n$\u0026gt;},长度为$n$。正如你所看到的,序列中的每个元素\u0026lt;$s_i$, $v_i$\u0026gt;都是一个有序对,其中有序对中的第一个元素$s_i$是左括号\u0027(\u0027或右括号\u0027)\u0027,而第二个元素$v_i$是一个整数。\u003c/p\u003e\n\n\u003cp\u003e由于BaoBao感到无聊,他决定玩一下这个序列。一开始,BaoBao的分数被设为0。每次BaoBao可以选择一个整数$k$,交换序列中第$k$个元素和第$(k+1)$个元素,并且只有当$1 \\le k \u0026lt; n$,$s_k \u003d$ \u0027(\u0027和$s_{k+1} \u003d$ \u0027)\u0027时,他的分数会增加$(v_k \\times v_{k+1})$。\u003c/p\u003e\n\n\u003cp\u003eBaoBao可以任意次数(包括零次)执行交换操作。BaoBao能够获得的最大可能分数是多少?\u003c/p\u003e\n\n\u003ch4\u003e输入\u003c/h4\u003e\n\u003cp\u003e包含多个测试用例。输入的第一行包含一个整数$T$,表示测试用例的数量。对于每个测试用例:\u003c/p\u003e\n\n\u003cp\u003e第一行包含一个整数$n$($1 \\le n \\le 10^3$),表示序列的长度。\u003c/p\u003e\n\n\u003cp\u003e第二行包含一个字符串$s$($|s| \u003d n$),由\u0027(\u0027和\u0027)\u0027组成。字符串中的第$i$个字符表示$s_i$,其含义如上所述。\u003c/p\u003e\n\n\u003cp\u003e第三行包含$n$个整数$v_1, v_2, \\dots, v_n$($-10^3 \\le v_i \\le 10^3$)。它们的含义如上所述。\u003c/p\u003e\n\n\u003cp\u003e保证所有测试用例的$n$之和不会超过$10^4$。\u003c/p\u003e\n\n\u003ch4\u003e输出\u003c/h4\u003e\n\u003cp\u003e对于每个测试用例,输出一行包含一个整数,表示BaoBao能够获得的最大可能分数。\u003c/p\u003e\n\n\u003ch4\u003e样例\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\u003e提示\u003c/h4\u003e\n\u003cp\u003e对于第一个样例测试用例,最佳策略是按顺序选择$k \u003d 2, 3, 5, 4$。\u003c/p\u003e\n\n\u003cp\u003e对于第二个样例测试用例,最佳策略是按顺序选择$k \u003d 2, 5$。\u003c/p\u003e"}}]}