eolymp
bolt
Try our new interface for solving problems
Məsələlər

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

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

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 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.

Giriş verilənləri

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

Çıxış verilənləri

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

prb800.gif

Nümunə

Giriş verilənləri #1
4 3 
1 15 2 
9 7 5 
9 2 4 
6 9 -1
Çıxış verilənləri #1
42 1