Простая максимальная сумма
Есть прямоугольная таблица размером 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 - количество строчек и количество столбиков (2 ≤ m ≤ 200, 2 ≤ n ≤ 40, m ≥ n), дальше в каждой из следующих m строк записано ровно n целых чисел (каждое не превышает по модулю 10^6) - значения клеток таблицы.
Выходные данные
Вывести два числа - максимальную сумму и количество путей.
