Максимальна сума з кількістю шляхів

Є прямокутна таблиця розміром 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 цілих чисел (кожне не перевищує за модулем 10^6) - значення клітинок таблиці.

Відомо, що шукана кількість шляхів з максимальною сумою не перевищує 10^9.

Вихідні дані

Вивести два цілих числа - максимальну суму та кількість шляхів.

Приклади

Примітка

У першому тесті максимальне значення 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.