← 返回题目列表

Codeforces · 2046/A

A. 交换列并查找路径

中文机器翻译题面 查看原题

有一个由 $$$2$$$ 行和 $$$n$$$ 列组成的矩阵。行从上到下编号为 $$$1$$$ 到 $$$2$$$;列从左到右编号为 $$$1$$$ 到 $$$n$$$。我们将第 $$$i$$$ 行和第 $$$j$$$ 列交叉处的单元格表示为 $$$(i,j)$$$。每个单元格包含一个整数;最初,单元格 $$$(i,j)$$$ 中的整数为 $$$a_{i,j}$$$。

您可以执行以下操作任意次数(可能为零):

- 选择两列并交换它们(即选择两个整数 $$$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)$$$,下一个单元格应为 $$$(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}, \ldots, a_{1,n}$$$ ($$$-10^5 \le a_{i,j} \le 10^5$$$) — 矩阵的第一行;
- 第三行包含 $$$n$$$ 整数 $$$a_{2,1}, a_{2,2}, \ldots, a_{2,n}$$$ ($$$-10^5 \le a_{i,j} \le 10^5$$$) — 矩阵的第二行。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$5000$$$。

输出

对于每个测试用例,打印一个整数 - 您可以获得的路径的最大成本。

示例

输入 #1

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

输出 #1

-5
16
29

注意

以下是示例的前三个测试用例的说明。左边的矩阵是输入中给出的矩阵,右边的矩阵是几次列交换后的矩阵状态(可能为零)。最佳路径以绿色突出显示。