MaxSum (Щаслива сума - 2)#5861
Вас чекає прямокутна таблиця розміром рядків і стовпців. Кожна клітинка містить невід'ємне ціле число. Ви можете рухатися по таблиці згори вниз, починаючи з будь-якої клітинки верхнього рядка. З клітинки можна перейти в одну з «нижніх сусідніх» клітин: (i+1, j-1), (i+1, j) або (i+1, j+1). Якщо j = M, перехід у (i+1, j+1) неможливий; якщо j = 1, перехід у (i+1, j-1) неможливий. Маршрут можна завершити в будь-якій клітинці нижнього рядка.
Напишіть програму, яка знайде максимальну можливу щасливу суму значень клітинок вздовж будь-якого допустимого шляху. Щасливим числом є таке додатне ціле число, десятковий запис якого складається лише з цифр і . Наприклад, , і – це щасливі числа; , , і – ні. Важливо, щоб саме сума виявилася щасливим числом, а не окремі доданки.
Перший рядок містить два цілих числа і (1 \leq N, M \leq 12) – кількість рядків і стовпців. Далі у кожному з наступних рядків записано по невід'ємних цілих чисел, розділених пробілами (кожне у десятковому записі містить не більше цифр) – це значення клітинок таблиці.
Виведіть найбільшу можливу щасливу суму серед усіх допустимих шляхів або impossible (без лапок, малими латинськими літерами), якщо жодна сума не є щасливим числом.
Приклад 1