题目内容

给定一个 $2 \times n$ 的矩阵，其中第 $i$ 行（$i=1,2$）第 $j$ 列（$1 \le j \le n$）的值为 $a_{i,j}$。你可以进行任意次操作：对于每个满足 $1 \le j < n$ 且 $j$ 为奇数的列，可以选择交换 $a_{1,j}$ 与 $a_{2,j+1}$，也可以选择交换 $a_{1,j+1}$ 与 $a_{2,j}$，两种交换相互独立。操作完成后，你从 $(1,1)$ 出发，每次只能向右或向下移动一格，最终到达 $(2,n)$，将沿途经过的所有格子（包括起点和终点）的值累加。你的目标是通过合适的交换和路径选择，使得累加和最大，并输出这个最大值。所有数值均为正整数。约束：列数 $n$ 不超过 $2 \times 10^5$，每个数值不超过 $10^9$，测试数据组数 $t$ 不超过 $10^4$，且所有测试数据的 $n$ 之和不超过 $2 \times 10^5$。

输入描述

第一行包含一个整数 $t$，表示测试数据组数。对于每组数据，第一行包含一个整数 $n$，接下来两行，每行包含 $n$ 个整数，分别表示矩阵第一行和第二行的数值。

输出描述

对于每组测试数据，输出一行一个整数，表示最大可获得的累加和。

样例1

输入

1
1
5
10

输出

15

说明

只有一列 $n=1$，无法进行任何交换操作。路径必须从 $(1,1)$ 向下移动到 $(2,1)$，经过的格子值为 $a_{1,1}=`5`$ 和 $a_{2,1}=`10`$，总和为 5 + 10 = 15。因此最大累加和为 15。

样例2

输入

1
2
1 4
2 3

输出

8

说明

矩阵只有一个小块 $(j=0, j=1)$，四个数为 $x=`1`$, $y=`4`$, $z=`2`$, $w=`3`$。可进行的交换为 $x \leftrightarrow w$ 和 $y \leftrightarrow z$。如果路径不在此小块内向下，最优贡献为 $\max(x,w)+\max(y,z)=\max(1,3)+\max(4,2)=`3`+`4`=`7`$。如果路径在此小块内向下，贡献为 $x+w+\max(y,z)=`1`+`3`+\max(4,2)=`4`+`4`=`8`$。因此最大累加和为 8。

样例3

输入

1
3
1 10 100
2 20 200

输出

330

说明

列数 $n=3$，包含一个完整小块 $(0,1)$ 和一列单独的第 $3$ 列。 小块 $(0,1)$ 的值：$x=`1`$, $y=`10`$, $z=`2`$, $w=`20`$。普通经过的贡献 $S=\max(1,20)+\max(10,2)=`20`+`10`=`30`$；若在该小块向下，额外收益 $\min(1,20)=`1`$。 最后一列（第 $3$ 列）无法交换，其值为 $a_{1,3}=`100`$, $a_{2,3}=`200`$。 有两种选择：

1. 在完整小块内向下，最后一列只能经过下方格子，总贡献 $=30+1+200=231$；
2. 在最后一列向下，此时会同时经过上下两个格子，总贡献 $=30+200+100=330$。 取最大值，答案为 330。

样例4

输入

1
4
5 2 8 6
3 9 7 4

输出

32

说明

$n=4$ 有两个完整小块：小块 $0$ 为列 1-2（值 $x=`5`$, $y=`2`$, $z=`3`$, $w=`9`$），小块 $1$ 为列 3-4（值 $x=`8`$, $y=`6`$, $z=`7`$, $w=`4`$）。 小块 $0$ 的普通贡献 $S_0=\max(5,9)+\max(2,3)=`9`+`3`=`12`$，向下额外收益 $\min(5,9)=`5`$。 小块 $1$ 的普通贡献 $S_1=\max(8,4)+\max(6,7)=`8`+`7`=`15`$，向下额外收益 $\min(8,4)=`4`$。 基础贡献总和 $=12+15=`27`$。 因为 $n$ 为偶数，路径必须在某个小块内向下，选择额外收益最大的小块 $0$，最终答案 $=27+5=`32`$。