Проста максимальна сума
У вас є прямокутна таблиця розміром m рядків на n стовпців, де в кожній клітинці записано число. Ви повинні пройти по цій таблиці зверху вниз, починаючи з будь-якої клітинки верхнього рядка. Кожного разу можна переходити в одну з "нижніх сусідніх" клітинок. Це означає, що з клітинки з координатами (i, j) можна перейти на одну з наступних: (i + 1, j - 1), (i + 1, j), або (i + 1, j + 1). Якщо j = n, можливі лише перший і другий варіанти, а якщо j = 1, то лише другий і третій. Маршрут завершується в будь-якій клітинці нижнього рядка.
Напишіть програму, яка визначить максимальну суму значень клітинок, через які можна пройти, та кількість шляхів, на яких ця сума досягається. Гарантується, що кількість шляхів не перевищує 10^9.
Вхідні дані
У першому рядку подано m і n - кількість рядків і стовпців відповідно (2 ≤ m ≤ 200, 2 ≤ n ≤ 40, m ≥ n). У кожному з наступних m рядків міститься рівно n цілих чисел (кожне з яких не перевищує за модулем 10^6) - значення клітинок таблиці.
Вихідні дані
Виведіть два числа: максимальну суму та кількість шляхів, які дають цю суму.
