MaxSum (відвідати усі стовбчики ходом коня)
Є прямокутна таблиця розміром 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" повинен виводитись лише у тому випадку, коли не існує жодного маршруту ходами коня, який проходить через усі стовбчики хоча б по одному разу.
Примітка: Для поля 4×3 є рівно чотири способи спуститись ходами коня, відвідавши кожен стовбчик:
Максимальна можлива сума 25 = 15 + 4 + 6 досягається на третьому з них.
Для поля 3×3 таких способів взагалі немає.