Максимальная сумма с количеством путей
Максимальная сумма с количеством путей
Имеется прямоугольная таблица размером n строк на m столбиков. В каждой клетке записано целое число. По ней можно пройти сверху вниз, начиная из любой клетки верхней строки, дальше каждый раз переходя в одну из "нижних соседних" клеток (иными словами, из клетки с номером (i, j) можно перейти на (i + 1, j - 1) или на (i + 1, j) или на (i + 1, j + 1); в случае j = m последний из трёх описанных вариантов становится невозможным, а в случае j = 1 - первый) и закончить маршрут в какой-нибудь клетке нижней строки.
Напишите программу, которая будет находить максимально возможную сумму значений пройденных клеток среди всех допустимых путей и количество путей, на которых эта сумма достигается.
Входные данные
В первой строке записаны n и m (1 ≤ n, m ≤ 200) - количество строк и количество столбцов. Дальше в каждой из следующих n строк записано ровно m целых чисел (каждое из которых не превышает по модулю 106) - значения клеток таблицы.
Известно, что искомое количество путей с максимальной суммой не превышает 109.
Выходные данные
Вывести два целых числа - максимальную сумму и количество путей.
Пояснение
В первом тесте максимальное значение 42 можно получить лишь по одному пути: 15 + 9 + 9 + 9). Во втором тесте максимальное значение 111 можно получить тремя способами: a[1][3] = 100, a[2][2] = 1, a[3][1] = 10, либо a[1][3] = 100, a[2][3] = 10, a[3][2] = 1, либо a[1][3] = 100, a[2][3] = 10, a[3][3] = 1.
4 3 1 15 2 9 7 5 9 2 4 6 9 -1
42 1
3 3 1 1 100 1 1 10 10 1 1
111 3