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

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

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

В первой cтроке записаны m и n - количество строчек и количество столбиков (2 ≤ m ≤ 200, 2 ≤ n ≤ 40, m ≥ n), дальше в каждой из следующих m строк записано ровно n целых чисел (каждое не превышает по модулю 106) - значения клеток таблицы.

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

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