Имеется прямоугольная таблица размером 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.