| Educational Codeforces Round 17 |
|---|
| Закончено |
Дана прямоугольная таблица 3 × n, в каждой клетке которой записано число. Разрешается переходить из клетки в клетку, если они имеют общую сторону.
Найдите такой путь из верхней левой в правую нижнюю клетку таблицы, чтобы никакая клетка таблицы не была посещена дважды, а сумма чисел, записанных в клетках найденного пути, была максимальной.
В первой строке следует целое положительное число n (1 ≤ n ≤ 105) — количество столбцов в таблице.
В следующих трёх строках следует по n целых чисел — описание таблицы, причём j-е число в i-й строке соответствует ячейке таблицы aij ( - 109 ≤ aij ≤ 109).
Выведите максимальную сумму чисел на пути из левой верхней в правую нижнюю клетку таблицы. Путь не должен посещать никакую клетку дважды.
3
1 1 1
1 -1 1
1 1 1
7
5
10 10 10 -1 -1
-1 10 10 10 10
-1 10 10 10 10
110
Путь для первого примера из условия:
Путь для второго примера:
