CF2046A.Swap Columns and Find a Path

有一个包含 $2$ 行 $n$ 列的矩阵。从上至下标号 $1,2$，从左到右标号 $1$ 到 $n$。记第 $i$ 横行第 $j$ 竖列的位置为 $(i,j)$，每个单元位置有一个整数。

你可以进行如下操作任意次（包括 $0$ 次）：

• 交换两列数字（找到整数 $x,y$ 满足 $1\le x\lt y\le n$，交换 $a_{1,x}$ 与 $a_{1,y}$，同时交换 $a_{2,x}$ 与 $a_{2,y}$）。

以上操作全部完成后，你需要找到一条从 $(1,1)$ 到 $(2,n)$ 的路径，每一次只能从 $(i,j)$ 移动到 $(i+1,j)$ 或 $(i,j+1)$。显然，路径无法走出这个矩形。

这条路径的分数为路径上所有 $(n+1)$ 个整数之和。你要进行上述的操作，并且找到最大可能的分数。

本题包含多组数据。第一行，一个整数 $t$ ($1\le t\le 5000$) 表示数据组数。

对于每组数据，输入三行：

• 第一行，一个整数 $n$ ($1\le n\le 5000$)，表示矩阵的列数。

• 第二行，$n$ 个整数 $a_{1,1},a_{1,2},\cdots,a_{1,n}$，表示矩阵的第一行。

• 第三行，$n$ 个整数 $a_{2,1},a_{2,2},\cdots,a_{2,n}$，表示矩阵的第二行。

保证所有 $n$ 之和不超过 $5000$。

对于每组数据，输出一个整数，表示你可以获得的最大分数。

翻译：HYdroKomide