AT_abc407_e [ABC407E] Most Valuable Parentheses

You are given a sequence of non-negative integers $ A = (A_1,\dots,A_{2N}) $ of length $ 2N $ . Define the score of a parenthesis sequence $ s $ of length $ 2N $ as follows: - For every position $ i $ where the $ i $ -th character of $ s $ is `)`, set $ A_i $ to $ 0 $ , then take the sum of all elements of $ A $ . Find the maximum possible score of a correct parenthesis sequence of length $ 2N $ . You are given $ T $ test cases; solve each. What is a correct parenthesis sequence?A correct parenthesis sequence is a string that can be reduced to the empty string by repeatedly removing substrings equal to `()`.

The input is given from Standard Input in the following format: > $ T $ $ \textrm{case}_1 $ $ \textrm{case}_2 $ $ \vdots $ $ \textrm{case}_T $ $ \textrm{case}_i $ represents the $ i $ -th test case. Each test case is given in the following format: > $ N $ $ A_1 $ $ A_2 $ $ \vdots $ $ A_{2N} $

Output $ T $ lines. The $ i $ -th line ( $ 1 \le i \le T $ ) should contain the answer for the $ i $ -th test case.

### Sample Explanation 1 In the first test case, choosing the correct parenthesis string `(())()` gives a score of $ 400+500+0+0+300+0=1200 $ . No correct parenthesis string yields a higher score, so the answer is $ 1200 $ . Note that, as in the second test case of this sample, the answer may exceed the 32-bit integer range. ### Constraints - $ 1 \le T \le 500 $ - $ 1 \le N \le 2 \times 10^{5} $ - For each input file, the sum of $ N $ over all test cases is at most $ 2 \times 10^{5} $ . - $ 0 \le A_i \le 10^{9} $ ( $ 1 \le i \le 2N $ ) - All input values are integers.