Swap Columns and Find a Path
Contest: Codeforces Round 990 (Div. 1)
Difficulty rating: 1200
Tags: greedy, sortings

There is a matrix consisting of $$$2$$$ rows and $$$n$$$ columns. The rows are numbered from $$$1$$$ to $$$2$$$ from top to bottom; the columns are numbered from $$$1$$$ to $$$n$$$ from left to right. Let's denote the cell on the intersection of the $$$i$$$-th row and the $$$j$$$-th column as $$$(i,j)$$$. Each cell contains an integer; initially, the integer in the cell $$$(i,j)$$$ is $$$a_{i,j}$$$.

You can perform the following operation any number of times (possibly zero):

- choose two columns and swap them (i. e. choose two integers $$$x$$$ and $$$y$$$ such that $$$1 \le x < y \le n$$$, then swap $$$a_{1,x}$$$ with $$$a_{1,y}$$$, and then swap $$$a_{2,x}$$$ with $$$a_{2,y}$$$).

After performing the operations, you have to choose a path from the cell $$$(1,1)$$$ to the cell $$$(2,n)$$$. For every cell $$$(i,j)$$$ in the path except for the last, the next cell should be either $$$(i+1,j)$$$ or $$$(i,j+1)$$$. Obviously, the path cannot go outside the matrix.

The cost of the path is the sum of all integers in all $$$(n+1)$$$ cells belonging to the path. You have to perform the operations and choose a path so that its cost is maximum possible.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 5000$$$). The description of the test cases follows.

Each test case consists of three lines:

- the first line contains one integer $$$n$$$ ($$$1 \le n \le 5000$$$) — the number of columns in the matrix;
- the second line contains $$$n$$$ integers $$$a_{1,1}, a_{1,2}, \ldots, a_{1,n}$$$ ($$$-10^5 \le a_{i,j} \le 10^5$$$) — the first row of the matrix;
- the third line contains $$$n$$$ integers $$$a_{2,1}, a_{2,2}, \ldots, a_{2,n}$$$ ($$$-10^5 \le a_{i,j} \le 10^5$$$) — the second row of the matrix.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5000$$$.

Output format:
For each test case, print one integer — the maximum cost of a path you can obtain.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
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.

Example input:
3
1
-10
5
3
1 2 3
10 -5 -3
4
2 8 5 3
1 10 3 4

Example output:
-5
16
29

Editorial:
We can divide the columns in the matrix into three different groups:
1. the columns where we go through the top cell;
2. the columns where we go through the bottom cell;
3. the columns where we go through both cells.
There should be exactly one column in the $$$3$$$-rd group — this will be the column where we shift from the top row to the bottom row. However, all other columns can be redistributed between groups $$$1$$$ and $$$2$$$ as we want: if we want to put a column into the $$$1$$$-st group, we put it before the column where we go down; otherwise, we put it after the column where we go down. So, we can get any distribution of columns between the $$$1$$$-st and the $$$2$$$-nd group.
Now let's consider the contribution of each column to the answer. Columns from the $$$1$$$-st group add $$$a_{1,i}$$$ to the answer, columns from the $$$2$$$-nd group add $$$a_{2,i}$$$, the column from the $$$3$$$-rd group adds both of these values. So, we can iterate on the index of the column where we go down, take $$$a_{1,i} + a_{2,i}$$$ for it, and take $$$\max(a_{1,j}, a_{2,j})$$$ for every other column. This works in $$$O(n^2)$$$, and under the constraints of the problem, it is enough.
However, it is possible to solve the problem in $$$O(n)$$$. To do so, calculate the sum of $$$\max(a_{1,j}, a_{2,j})$$$ over all columns. Then, if we pick the $$$i$$$-th column as the column where we go down, the answer be equal to this sum, plus $$$\min(a_{1,i}, a_{2,i})$$$, since this will be the only column where we visit both cells.