AT_arc206_e [ARC206E] Rectangle Coloring

有一个 $N\times N$ 的棋盘，其中 $N$ 至少为 $4$。棋盘最外层边界上但不在四个角上的格子称为好格子。更正式地说，对于 $1\leq i,j \leq N$，且 $i=1$ 或 $i=N$ 或 $j=1$ 或 $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)$。然后将满足 $\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)$ 的所有格子染成黑色。每次操作的代价等于所选两好格子上整数之和。 请你计算将所有格子全部染黑所需的最小总代价。 对于 $T$ 组测试数据，分别输出答案。

输入由标准输入给出，格式如下： > $T$ $\mathrm{case}_1$ $\vdots$ $\mathrm{case}_T$ 每组测试数据格式如下： > $N$ $U_1$ ... $U_{N-2}$ $D_1$ ... $D_{N-2}$ $L_1$ ... $L_{N-2}$ $R_1$ ... $R_{N-2}$

输出 $T$ 行。 第 $i$ 行输出第 $i$ 组测试数据的答案。

### 样例解释 1 在第 $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$ 组测试数据的棋盘如下图所示：  ### 数据范围 - 所有输入均为整数。 - $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$。 由 ChatGPT 5 翻译