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](https://www.luogu.com.cn/user/299883)

Here are the explanations of the first three test cases of the example. The left matrix is the matrix given in the input, the right one is the state of the matrix after several column swaps (possibly zero). The optimal path is highlighted in green.