分数: 800 点
问题陈述
有一个 N\times N 板,在哪里 N 至少 4。板子最外边缘不是角的单元格称为好单元格。更正式地说,其中 (i,j) 这样 1\leq i,j \leq N 和 i=1 or i=N or j=1 or j=N,排除的单元格 (1,1),(1,N),(N,1),(N,N) 被称为好细胞。在这里, (r,c) 指行中的单元格 r 和专栏 c.
所有好的单元格上都写有整数。该信息以四个长度的整数序列给出 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)。对于所有人 (i,j) 满意 \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) 黑色。 操作的成本是写入两个选定的好单元格上的整数之和。
求将所有单元格涂成黑色所需的最小总成本。
回答 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-st 测试用例,您可以将所有单元格涂成黑色,如下所示:
- 执行选择操作 (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-nd 和 3-rd测试用例,输入板如下图所示:
