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

Простая максимальная сумма

Простая максимальная сумма

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Есть прямоугольная таблица размером m строк на n столбцов. В каждой клетке записано число. По ней нужно пройти сверху вниз, начиная с любой клетки верхней строки, каждый раз переходя в одну из "нижних соседних" клеток (иными словами, из клетки с номером (i, j) можно перейти или на (i + 1, j - 1), или на (i + 1, j), или на (i + 1, j + 1); в случае j = n возможны только 1-й и 2-й из трёх описанных вариантов, в случае j = 1 только 2-й и 3-й) и закончить маршрут в какой-нибудь клетке нижней строки.

Напишите программу, которая будет находить максимально возможную сумму значений пройденных клеток среди всех допустимых путей и количество путей, на которых эта сумма достигается. Гарантируется, что количество путей не превосходит 10^9.

Входные данные

В первой cтроке записаны m и n - количество строчек и количество столбиков (2m200, 2n40, mn), дальше в каждой из следующих m строк записано ровно n целых чисел (каждое не превышает по модулю 10^6) - значения клеток таблицы.

Выходные данные

Вывести два числа - максимальную сумму и количество путей.

prb800.gif

Пример

Входные данные #1
4 3 
1 15 2 
9 7 5 
9 2 4 
6 9 -1
Выходные данные #1
42 1