{"raw_statement":[{"iden":"problem statement","content":"There is an $N\\times N$ board, where $N$ is at least $4$. The cells on the outermost edge of the board that are not corners are called good cells. More formally, among $(i,j)$ such that $1\\leq i,j \\leq N$ and $i=1$ or $i=N$ or $j=1$ or $j=N$, the cells excluding $(1,1),(1,N),(N,1),(N,N)$ are called good cells. Here, $(r,c)$ refers to the cell in row $r$ and column $c$.\nAll good cells have integers written on them. This information is given as four integer sequences of length $N-2$: $U=(U_1,\\ldots,U_{N-2}),D=(D_1,\\ldots,D_{N-2}),L=(L_1,\\ldots,L_{N-2}),R=(R_1,\\ldots,R_{N-2})$.\nEach element of these integer sequences corresponds to the integer written on a good cell as follows:\n\n*   $U_i$: $(1,i+1)$\n*   $D_i$: $(N,i+1)$\n*   $L_i$: $(i+1,1)$\n*   $R_i$: $(i+1,N)$\n\nAlso, all cells on the board are initially colored white. You can perform the following operation any number of times:\n\n*   Choose two good cells that have never been chosen in any previous operation. Let the two chosen good cells be $(r_1,c_1)$ and $(r_2,c_2)$. For all $(i,j)$ satisfying $\\min(r_1,r_2)\\leq i \\leq \\max(r_1,r_2)$ and $\\min(c_1,c_2)\\leq j \\leq \\max(c_1,c_2)$, color $(i,j)$ black. The cost of the operation is the sum of the integers written on the two chosen good cells.\n\nFind the minimum total cost required to color all cells black.\nAnswer for $T$ test cases."},{"iden":"constraints","content":"*   All input values are integers.\n*   $1 \\leq T \\leq 12500$\n*   $4 \\leq N \\leq 5\\times 10^4$\n*   $0\\leq U_i,D_i,L_i,R_i \\leq 10^9$\n*   The sum of $N$ over all test cases does not exceed $5\\times 10^4$."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$T$\n$\\mathrm{case}_1$\n$\\vdots$\n$\\mathrm{case}_T$\n\nEach test case is given in the following format:\n\n$N$\n$U_1$ $\\ldots$ $U_{N-2}$\n$D_1$ $\\ldots$ $D_{N-2}$\n$L_1$ $\\ldots$ $L_{N-2}$\n$R_1$ $\\ldots$ $R_{N-2}$"},{"iden":"sample input 1","content":"3\n4\n1 2\n5 6\n7 8\n3 4\n6\n6 2 10 2\n7 1 3 0\n2 4 4 2\n2 10 6 4\n8\n5 0 6 10 1 8\n5 5 9 9 4 7\n7 3 4 9 7 6\n10 9 0 4 10 5"},{"iden":"sample output 1","content":"36\n15\n21\n\nIn the $1$\\-st test case, you can color all cells black as follows:\n\n*   Perform the operation choosing $(1,2)$ and $(3,4)$.\n*   Perform the operation choosing $(2,4)$ and $(4,2)$.\n*   Perform the operation choosing $(4,3)$ and $(2,1)$.\n*   Perform the operation choosing $(3,1)$ and $(1,3)$.\n\nThe total cost is $(1+4)+(3+5)+(6+7)+(8+2)=36$.\n![image](https://img.atcoder.jp/arc206/70f2b55f8ba2310c24707b33dd4589f1.png)\nFor the $2$\\-nd and $3$\\-rd test cases, the input boards are illustrated below:\n![image](https://img.atcoder.jp/arc206/9b0d44ca21342b6e386fc4492ebe61fd.png)"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}