{"raw_statement":[{"iden":"problem statement","content":"In this problem, we consider strings consisting of `(`, `)`, `[`, and `]`.\nA string $x$ is said to be a **good parentheses sequence** if and only if **one** of the following conditions is satisfied:\n\n*   $x$ is an empty sequence.\n*   There is a good parentheses sequence $s$ such that concatenating `(`, $s$, and `)` in this order results in $x$.\n*   There is a good parentheses sequence $s$ such that concatenating `[`, $s$, and `]` in this order results in $x$.\n*   There are non-empty good parentheses sequences $s$ and $t$ such that concatenating $s$ and $t$ in this order results in $x$.\n\nFor example, `[]`, `([()])`, and `()[()]` are good parentheses sequences, but neither `())` nor `([)]` is a good parentheses sequence.\nGiven are an even number $N$ and integer sequences $A$ and $B$ of length $N$ each. Here, we define a score for a good parentheses sequence of length $N$, $s=s_1s_2\\cdots s_N$, as follows:\n\n*   The score for $s$ is the sum of the scores of its characters.\n*   The score for the $i$\\-th character ($1 \\leq i \\leq N$) is $A_i$ if $s_i$ is `(` or `)`, and $B_i$ if $s_i$ is `[` or `]`.\n\nFind the maximum possible score for a good parentheses sequence of length $N$."},{"iden":"constraints","content":"*   $2 \\leq N \\leq 10^5$\n*   $N$ is an even number.\n*   $1 \\leq A_i \\leq 10^9$\n*   $1 \\leq B_i \\leq 10^9$\n*   All numbers in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$A_1$ $A_2$ $\\cdots$ $A_N$\n$B_1$ $B_2$ $\\cdots$ $B_N$"},{"iden":"sample input 1","content":"4\n4 2 3 1\n2 3 2 4"},{"iden":"sample output 1","content":"12\n\nFor $s=$`()[]`, the score is $A_1+A_2+B_3+B_4=12$, which is the maximum possible value."},{"iden":"sample input 2","content":"10\n866111664 844917655 383133839 353498483 472381277 550309930 378371075 304570952 955719384 705445072\n178537096 218662351 231371336 865935868 579910117 62731178 681212831 16537461 267238505 318106937"},{"iden":"sample output 2","content":"6629738472"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}