
ZOJ Problem Set  4027
BaoBao has just found a strange sequence {<$s_1$, $v_1$>, <$s_2$, $v_2$>, $\dots$, <$s_n$, $v_n$>} of length $n$ in his pocket. As you can see, each element <$s_i$, $v_i$> in the sequence is an ordered pair, where the first element $s_i$ in the pair is the left parenthesis '(' or the right parenthesis ')', and the second element $v_i$ in the pair is an integer. As BaoBao is bored, he decides to play with the sequence. At the beginning, BaoBao's 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 < n$, $s_k =$ '(' and $s_{k+1} =$ ')'. BaoBao is allowed to perform the swapping any number of times (including zero times). What's the maximum possible score BaoBao can get? InputThere are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case: The first line contains an integer $n$ ($1 \le n \le 10^3$), indicating the length of the sequence. The second line contains a string $s$ ($s = n$) consisting of '(' and ')'. The $i$th character in the string indicates $s_i$, of which the meaning is described above. The 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. It's guaranteed that the sum of $n$ of all test cases will not exceed $10^4$. OutputFor each test case output one line containing one integer, indicating the maximum possible score BaoBao can get. Sample Input4 6 )())() 1 3 5 1 3 2 6 )())() 1 3 5 100 3 2 3 ()) 1 1 1 3 ()) 1 1 1 Sample Output24 21 0 2 HintFor the first sample test case, the optimal strategy is to select $k = 2, 3, 5, 4$ in order. For the second sample test case, the optimal strategy is to select $k = 2, 5$ in order. Author: WENG, Caizhi Source: The 15th Zhejiang Provincial Collegiate Programming Contest Sponsored by TuSimple 