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