Емблема центру  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


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