Дана матрица, состоящая из \(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)\) ячейках, принадлежащих пути. Вам нужно выполнить операции и выбрать путь так, чтобы его стоимость была максимальной.
Примечание
Ниже приведены объяснения первых трех наборов входных данных из примера. Левая матрица — это матрица, заданная во входных данных, правая — состояние матрицы после нескольких (возможно, нуля) перестановок столбцов. Оптимальный путь выделен зеленым цветом.
