Five for week 14 (2013-2014)
Счастливая сумма 3
Есть прямоугольная таблица размером N строк на M столбиков. В каждой клетке записано целое число. По ней нужно пройти сверху вниз, начиная из любой клетки верхней строки, дальше каждый раз переходя в одну из "нижних соседних" клеток (иными словами, из клетки с номером (i, j) можно перейти или на (i+1, j–1), или на (i+1, j), или на (i+1, j+1); в случае j=M последний из трёх описанных вариантов становится невозможным, а в случае j=1 — первый) и закончить маршрут в какой-нибудь клетке нижней строки.
Напишите программу, которая будет находить максимально возможную счастливую сумму значений пройденных клеток среди всех допустимых путей. В данной задаче даётся нестандартное определение счастливого числа: счастливыми являются натуральные числа, в десятичной записи которых содержится по крайней мере две цифры, и при этом две последние (младшие) — счастливые цифры 4 и/или 7. Например, числа 47, 744, 6328674 являются счастливыми, а 0, 4, 5, 44747467 — не являются. Обратите внимание, что счастливой должна быть именно сумма, а не отдельные слагаемые.
Input data
В первой строке записаны N и M — количество строчек и количество столбиков (1 ≤ N, M ≤ 444), дальше в каждой из следующих N строк записано ровно по M разделённых пробелами целых чисел (каждое принадлежит диапазону 0 ≤ aij ≤ 444) — значения клеток таблицы.
Output data
Вывести либо единственное натуральное число (найденную максимальную среди счастливых сумм), либо строку "impossible" (без кавычек, маленькими латинскими буквами). Строка "impossible" должна выводиться только в случае, когда среди маршрутов указанного вида нет ни одного со счастливой суммой.
Examples
3 4 8 2 10 14 22 2 15 25 1 14 9 1
44