A. Переставьте столбцы и найдите путь
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана матрица, состоящая из $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — максимальную стоимость пути, которую вы можете получить.

Пример
Входные данные
3
1
-10
5
3
1 2 3
10 -5 -3
4
2 8 5 3
1 10 3 4
Выходные данные
-5
16
29
Примечание

Ниже приведены объяснения первых трех наборов входных данных из примера. Левая матрица — это матрица, заданная во входных данных, правая — состояние матрицы после нескольких (возможно, нуля) перестановок столбцов. Оптимальный путь выделен зеленым цветом.