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