Альтернативні шляхи
Задано прямокутну таблицю розміром M рядків на N стовбчиків. У кожній клітинці записано натуральне число, яке не перевищує 200. Мандрівник повинен пройти по цій таблиці з лівого верхнього кута у правий нижній, на кожному кроці переміщуючись або на 1 клітинку направо, або на 1 клітинку вниз. Очевидно, таких шляхів багато. Для кожного шляху можна обчислити суму чисел у пройдених клітинках. Сред цих сум, очевидно, є максимальна. Будемо поблажливими до Мандрівника, вважаючи "гарними" не лише шляхи, на яких у точності досягається максимально можлива сума, а ще й шляхи, сума яких відрізняється від максимальної не більше ніж на K. Кількість "гарних" шляхів гарантовано не перевищує 10^9.
Напишіть програму, яка знаходить значення максимально можливої суми та кількість "гарних" шляхів.
Вхідні дані
Перший рядок містить три цілих числа M (2 ≤ M ≤ 200), N (2 ≤ N ≤ 200) та K (0 ≤ K ≤ 200). Кожен з наступних M рядків містить N чисел, записаних у відповідних клітинках.
Вихідні дані
Перший рядок повинен містити максимальну можливу суму; другий рядок - кількість маршрутів, сума чисел яких відрізняється від максимальної не більше ніж на K.