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

MaxSum (Щаслива сума - 2)

MaxSum (Щаслива сума - 2)

Ліміт часу 4 секунди
Ліміт використання пам'яті 64 MiB

Є прямокутна таблиця розміром N рядків на M стовбчиків. У кожній клітинці записано ціле число. По ній можна пройти зверху вниз, починаючи з довільної клітинки верхнього рядка, далі кожного разу переходячи в одну з "нижніх сусідніх" клітинок (іншими словами, з клітинки під номером (i, j) можна перейти або на (i+1, j-1), або на (i+1, j), або на (i+1, j+1); у випадку j=M останній з трьох описаних варіантів стає неможливи, а у випадку j=1 - перший) і завершити маршрут у якій-небудь клітинці нижнього рядка.

Напишіть програму, яка буде знаходити максимально можливу щасливу суму значень пройдених клітинок серед усеі допустимих шляхів. Усім відомо, що щасливими є натуральні числа, у десятковому запису яких містяться лише щасливі цифры 4 та 7. Наприклад, числа 47, 744, 4 є щасливими, а 0, 5, 17, 467 - ні. Зверніть увагу, що щасливою повинна бути саме сума, а не окремі доданки.

Вхідні дані

У першому рядку записані N та M - кількість рядків та кількість стовбчиків (1N, M12), далі у кожному з наступних N рядків записано рівно M відокремлених пропусками цалих невід'ємних чисел (кожне з яких має у десятковому запису не більше 12 цифр) - значення клітинок таблиці.

Вихідні дані

Вивести або єдине ціле число (знайдену максимальну серед сум по маршрутам вказаного виду), або рядок "impossible" (без лапок, маленькими латинськими буквами). Рядок "impossible" повинен виводитись лише у тому випадку, коли серед маршрутів вказаного виду немає жодного зі щасливою сумою.

Приклад

Вхідні дані #1
3 4
3 0 10 10
5 0 7 4
4 10 5 4
Вихідні дані #1
7
Автор Ілля Порубльов
Джерело Літня школа Севастополь 2013, Хвиля 1, День 2