Дана прямоугольная таблица 3 × n, в каждой клетке которой записано число. Разрешается переходить из клетки в клетку, если они имеют общую сторону.
Найдите такой путь из верхней левой в правую нижнюю клетку таблицы, чтобы никакая клетка таблицы не была посещена дважды, а сумма чисел, записанных в клетках найденного пути, была максимальной.
Выходные данные
Выведите максимальную сумму чисел на пути из левой верхней в правую нижнюю клетку таблицы. Путь не должен посещать никакую клетку дважды.
Примечание
Путь для первого примера из условия:
Путь для второго примера:
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 1 1
1 -1 1
1 1 1
|
7
|
|
2
|
5
10 10 10 -1 -1
-1 10 10 10 10
-1 10 10 10 10
|
110
|