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 - Экзамен