eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

MaxSum (посетить все столбики ходами коня)

MaxSum (посетить все столбики ходами коня)

Лимит времени 4 секунды
Лимит использования памяти 64 MiB

Есть прямоугольная таблица размером N строк на M столбиков. В каждой клетке записано целое число. По ней нужно пройти сверху вниз, начиная из любой клетки верхней строки, дальше двигаясь вниз ходами коня и закончить маршрут в какой-нибудь клетке нижней строки. То есть, из клетки (i, j) можно перейти в (i+1, j–2), или в (i+2, j–1), или в (i+2, j + 1), или в (i+1, j + 2), исключая варианты, выходящие за пределы доски.

Напишите программу, которая будет находить максимально возможную сумму значений пройденных клеток среди всех допустимых путей ходами коня, проходящих хотя бы по одному разу через каждый из столбиков.

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

В первой строке записаны N и M - количество строчек и количество столбиков (1 ≤ N ≤ 42, 1 ≤ M ≤ 17); дальше в каждой из следующих N строк записано ровно M разделённых пробелами целых чисел (каждое не превышает по модулю 10^6) - значения клеток таблицы.

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

Вывести либо единственное целое число (найденную максимальную среди сумм по маршрутам указанного вида), либо строку "impossible" (без кавычек, маленькими латинскими буквами). Строка "impossible" должна выводиться только в том случае, когда не существует ни одного маршрута ходами коня, проходящего через все столбики хотя бы по одному разу.

Пример

Входные данные #1
4 3
1 15 2
9 7 5
9 2 4
6 9 -1
Выходные данные #1
25
Входные данные #2
3 3
1 15 2
9 7 5
9 2 4
Выходные данные #2
impossible

Примечание

Для поля 4×3 есть ровно четыре способа спуститься ходами коня, посетив каждый столбик:

Первый - a[1][1]->a[2][3]->a[4][2]

Второй - a[1][2]->a[3][1]->a[4][3]

Третий - a[1][2]->a[3][3]->a[4][1]

Четвертый - a[1][3]->a[2][1]->a[4][2]

Максимальная возможная сумма 25 = 15 + 4 + 6 достигается на третьем из них.

Для поля 3×3 таких способов вообще нет.

Автор Илья Порублёв
Источник Летняя школа Севастополь 2013, Волна 1, День 2