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

Счастливая сумма 3

Счастливая сумма 3

Есть прямоугольная таблица размером \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} --- первый) и закончить маршрут в какой-нибудь клетке нижней строки. Напишите программу, которая будет находить максимально возможную \textit{счастливую сумму} значений пройденных клеток среди всех допустимых путей. \textit{В данной задаче даётся нестандартное определение счастливого числа}: счастливыми являются натуральные числа, в десятичной записи которых содержится по крайней мере две цифры, и при этом две последние (младшие) --- счастливые цифры \textbf{4} и/или \textbf{7}. Например, числа \textbf{47}, \textbf{744}, \textbf{6328674} являются счастливыми, а \textbf{0}, \textbf{4}, \textbf{5}, \textbf{44747467} --- не являются. Обратите внимание, что счастливой должна быть именно сумма, а не отдельные слагаемые. \InputFile В первой строке записаны \textbf{N} и \textbf{M} --- количество строчек и количество столбиков (\textbf{1} ≤ \textbf{N}, \textbf{M} ≤ \textbf{444}), дальше в каждой из следующих \textbf{N} строк записано ровно по \textbf{M} разделённых пробелами целых чисел (каждое принадлежит диапазону \textbf{0} ≤ \textbf{a}_\{ij \}≤ \textbf{444}) --- значения клеток таблицы. \OutputFile Вывести либо единственное натуральное число (найденную максимальную среди счастливых сумм), либо строку "\textbf{impossible}" (без кавычек, маленькими латинскими буквами). Строка "\textbf{impossible}" должна выводиться только в случае, когда среди маршрутов указанного вида нет ни одного со счастливой суммой.
Лимит времени 3 секунды
Лимит использования памяти 256 MiB
Входные данные #1
3 4
8 2 10 14
22 2 15 25
1 14 9 1
Выходные данные #1
44
Автор Илья Порублёв
Источник Летняя школа Севастополь 2013, Волна 1, День 7 - Экзамен