/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 800 点
問題文
N\times N の盤面があります．ここで N は 4 以上です．盤面の最も外側かつ角でないマスを，良いマスと呼びます．より厳密には，1\leq i,j \leq N であって，i=1 または i=N または j=1 または j=N であるような (i,j) のうち，(1,1),(1,N),(N,1),(N,N) を除いたマスを良いマスと呼びます．ここで，(r,c) は r 行 c 列目のマスを指します．
全ての良いマスには整数が書いてあります．この情報は， 4 個の長さ 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}) として与えられます．
この整数列の各要素は，以下のように良いマスに書かれた整数と対応しています．
- U_i：(1,i+1)
- D_i：(N,i+1)
- L_i：(i+1,1)
- R_i：(i+1,N)
また，盤面の全てのマスは初め白色で塗られています．あなたは以下の操作を何回でも行えます．
- これまでの操作で一度も選ばれていない良いマスを二つ選ぶ．選んだ二つの良いマスを (r_1,c_1) と (r_2,c_2) として，\min(r_1,r_2)\leq i \leq \max(r_1,r_2)かつ \min(c_1,c_2)\leq j \leq \max(c_1,c_2)を満たす全ての (i,j) に対して，(i,j) を黒く塗る． 操作にかかるコストは選んだ二つの良いマスに書かれている整数の和である．
全てのマスを黒くするために必要なコストの総和の最小値を求めてください．
T 個のテストケースについて答えてください．
制約
- 入力される数値は全て整数
- 1 \leq T \leq 12500
- 4 \leq N \leq 5\times 10^4
- 0\leq U_i,D_i,L_i,R_i \leq 10^9
- 全てのテストケースにわたる N の総和は 5\times 10^4 を超えない
入力
入力は以下の形式で標準入力から与えられる．
T
\mathrm{case}_1
\vdots
\mathrm{case}_T
各テストケースは以下の形式で与えられる．
N
U_1 \ldots U_{N-2}
D_1 \ldots D_{N-2}
L_1 \ldots L_{N-2}
R_1 \ldots R_{N-2}
出力
T 行出力せよ．
i 行目には，i 番目のテストケースの答えを出力せよ．
入力例 1
3 4 1 2 5 6 7 8 3 4 6 6 2 10 2 7 1 3 0 2 4 4 2 2 10 6 4 8 5 0 6 10 1 8 5 5 9 9 4 7 7 3 4 9 7 6 10 9 0 4 10 5
出力例 1
36 15 21
1 番目のテストケースでは，
- (1,2) と (3,4) を選んで操作
- (2,4) と (4,2) を選んで操作
- (4,3) と (2,1) を選んで操作
- (3,1) と (1,3) を選んで操作
とすると，全てのマスを黒くすることができます．コストの総和は，(1+4)+(3+5)+(6+7)+(8+2)=36 です．
2 番目，3 番目のテストケースについて，入力される盤面を図示すると次のようになります．
Score : 800 points
Problem Statement
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.
All 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}).
Each element of these integer sequences corresponds to the integer written on a good cell as follows:
- U_i: (1,i+1)
- D_i: (N,i+1)
- L_i: (i+1,1)
- R_i: (i+1,N)
Also, all cells on the board are initially colored white. You can perform the following operation any number of times:
- 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.
Find the minimum total cost required to color all cells black.
Answer for T test cases.
Constraints
- All input values are integers.
- 1 \leq T \leq 12500
- 4 \leq N \leq 5\times 10^4
- 0\leq U_i,D_i,L_i,R_i \leq 10^9
- The sum of N over all test cases does not exceed 5\times 10^4.
Input
The input is given from Standard Input in the following format:
T
\mathrm{case}_1
\vdots
\mathrm{case}_T
Each test case is given in the following format:
N
U_1 \ldots U_{N-2}
D_1 \ldots D_{N-2}
L_1 \ldots L_{N-2}
R_1 \ldots R_{N-2}
Output
Output T lines.
For the i-th line, output the answer for the i-th test case.
Sample Input 1
3 4 1 2 5 6 7 8 3 4 6 6 2 10 2 7 1 3 0 2 4 4 2 2 10 6 4 8 5 0 6 10 1 8 5 5 9 9 4 7 7 3 4 9 7 6 10 9 0 4 10 5
Sample Output 1
36 15 21
In the 1-st test case, you can color all cells black as follows:
- Perform the operation choosing (1,2) and (3,4).
- Perform the operation choosing (2,4) and (4,2).
- Perform the operation choosing (4,3) and (2,1).
- Perform the operation choosing (3,1) and (1,3).
The total cost is (1+4)+(3+5)+(6+7)+(8+2)=36.
For the 2-nd and 3-rd test cases, the input boards are illustrated below: