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