Задача MSLPRIM. Есть прямоугольная таблица размером 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 такими не является. Обратите внимание, что счастливой должна быть именно сумма, а не отдельные слагаемые.
Технические условия. Программа MSLPRIM читает с устройства стандартного ввода через пробел числа N и M (1<=N,M<=77), далее з каждой из последующих N строк по M разделенных пробелом целых неотрицательных чисел (каждое не превышает 77) – значения клеток таблицы. Программа выводит на устройство стандартного вывода единственное натуральное число – максимальную счастливую сумму либо -1, если среди маршрутов нет ни одного со счастливой суммой.
Пример
Ввод
3 4
8 2 10 4
22 2 15 25
1 14 9 1
Вывод
44