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

MaxSum (Счастливая сумма - 1)

MaxSum (Счастливая сумма - 1)

Есть прямоугольная таблица размером \textbf{N} строк на \textbf{M} столбиков. В каждой клетке записано целое число. По ней можно пройти сверху вниз, начиная из любой клетки верхней строки, дальше каждый раз переходя в одну из "нижних соседних" клеток (иными словами, из клетки с номером (\textbf{i}, \textbf{j}) можно перейти или на (\textbf{i+1}, \textbf{j-1}), или на (\textbf{i+1}, \textbf{j}), или на (\textbf{i+1}, \textbf{j+1}); в случае \textbf{j=M} последний из трёх описанных вариантов становится невозможным, а в случае \textbf{j=1} - первый) и закончить маршрут в какой-нибудь клетке нижней строки. Напишите программу, которая будет находить максимально возможную счастливую сумму значений пройденных клеток среди всех допустимых путей. Всем известно, что счастливыми являются натуральные числа, в десятичной записи которых содержатся только счастливые цифры \textbf{4} и \textbf{7}. Например, числа \textbf{47}, \textbf{744}, \textbf{4} являются счастливыми, а \textbf{0}, \textbf{5}, \textbf{17}, \textbf{467} - не являются. Обратите внимание, что счастливой должна быть именно сумма, а не отдельные слагаемые. \InputFile В первой строке записаны \textbf{N} и \textbf{M} - количество строчек и количество столбиков (\textbf{1} ≤ \textbf{N}, \textbf{M} ≤ \textbf{77}), дальше в каждой из следующих \textbf{N} строк записано ровно \textbf{M} разделённых пробелами целых чисел (которое принадлежит диапазону \textbf{0} ≤ \textbf{a}_\{ij \}≤ \textbf{77}) - значения клеток таблицы. \OutputFile Вывести либо единственное целое число (найденную максимальную среди сумм по маршрутам указанного вида), либо строку "\textbf{impossible}" (без кавычек, маленькими латинскими буквами). Строка "\textbf{impossible}" должна выводиться только в том случае, когда среди маршрутов указанного вида нет ни одного со счастливой суммой.
Лимит времени 4 секунды
Лимит использования памяти 64 MiB
Входные данные #1
3 4
8 2 10 14
22 2 15 25
1 14 9 1
Выходные данные #1
44
Автор Илья Порублёв
Источник Летняя школа Севастополь 2013, Волна 1, День 2