交换列并寻找路径

https://codeforces.com/problemset/problem/2046/A

有一个矩阵，共有 \(2\) 行 \(n\) 列。行从上到下编号为 \(1\) 到 \(2\)，列从左到右编号为 \(1\) 到 \(n\)。我们用单元格 \((i,j)\) 表示第 \(i\) 行第 \(j\) 列。每个单元格 \((i,j)\) 内初始包含一个整数 \(a_{i,j}\)。

你可以进行任意次（可能为 \(0\) 次）如下操作：

选择两个列号 \(x\) 和 \(y\)，满足 \(1 \le x < y \le n\)，然后执行：

交换 \(a_{1,x}\) 和 \(a_{1,y}\)

同时交换 \(a_{2,x}\) 和 \(a_{2,y}\)

完成操作后，你需要选择一条路径，从左上角单元格 \((1,1)\) 走到右下角单元格 \((2,n)\)。路径中除了最后一个格子以外，每一步只能向右（\((i,j) \to (i,j+1)\)）或向下（\((i,j) \to (i+1,j)\)）走，不能走出矩阵边界。

该路径的代价定义为路径上所有格子中整数之和。路径总共会经过 \(n+1\) 个单元格。

你的任务是，经过若干列交换后，选择一条路径，使得路径的代价最大。

输入格式 每个测试用例包含多个数据组。第一行包含一个整数 \(t\)（\(1 \le t \le 5000\)），表示数据组的数量。

接下来每组测试用例包含三行：

第一行一个整数 \(n\)（\(1 \le n \le 5000\)），表示矩阵的列数；

第二行 \(n\) 个整数 \(a_{1,1}, a_{1,2}, \dots, a_{1,n}\)，表示矩阵第一行的值；

第三行 \(n\) 个整数 \(a_{2,1}, a_{2,2}, \dots, a_{2,n}\)，表示矩阵第二行的值。

保证所有测试用例中 \(n\) 的总和不超过 \(5000\)。

输出格式

对于每组测试用例，输出一行一个整数，表示该测试用例中路径的最大代价。

输入示例

3
1
-10
5
3
1 2 3
10 -5 -3
4
2 8 5 3
1 10 3 4

输出示例

-5
16
29

测试用例解说