{"problem":{"name":"Bracket Score","description":{"content":"In this problem, we consider strings consisting of `(`, `)`, `[`, and `]`. A string $x$ is said to be a **good parentheses sequence** if and only if **one** of the following conditions is satisfied: ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc048_b"},"statements":[{"statement_type":"Markdown","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$.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nInput 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc048_b","tags":[],"sample_group":[["4\n4 2 3 1\n2 3 2 4","12\n\nFor $s=$`()[]`, the score is $A_1+A_2+B_3+B_4=12$, which is the maximum possible value."],["10\n866111664 844917655 383133839 353498483 472381277 550309930 378371075 304570952 955719384 705445072\n178537096 218662351 231371336 865935868 579910117 62731178 681212831 16537461 267238505 318106937","6629738472"]],"created_at":"2026-03-03 11:01:14"}}