Емблема центру  www.olymp.vinnica.ua     netoi.org.ua
Центр олімпіад школярів в Iнтернеті
Likt-PMG17
м.Вiнниця


Годинник
 
MSL

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

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

Технічні умови. Програма MSL читає з пристрою стандартного введення через пропуск числа N і M (1<=N,M<=12),  далі  з кожного з наступних  N рядків по M розділених пропуском цілих невід’ємних чисел (кожне містить у десятковому запису не більше 12 цифр) – значення клітинок таблиці. Програма виводить на пристрій стандартного виведення єдине натуральне число – максимальну щасливу суму або -1, якщо серед маршрутів немає жодного зі щасливою сумою.

Приклад

Введення

3 4

3 0 10 10

5 0 7 4

4 10 5 4

Виведення

7


© Всеукраїнський віртуальний центр олімпіад школярів "ОЛІМП"