Problems
Альтернативные пути
Альтернативные пути
Задано прямоугольную таблицу размером \textbf{M} строк на \textbf{N} столбиков. В каждой клеточке записано натуральное число, не превышающее \textbf{200}. Путник должен пройти по этой таблице из левого верхнего угла в правый нижний, на каждом шаге перемещаясь либо на \textbf{1} клеточку направо, либо на \textbf{1} клеточку вниз. Очевидно, таких путей много. Для каждого пути можно вычислить сумму чисел в пройденных клеточках. Среди этих сумм, очевидно, есть максимальная. Будем снисходительными к Путнику, считая "хорошими" не только пути, на которых в точности достигается максимально возможная сумма, а еще и пути, сумма которых отличается от максимальной не более чем на \textbf{K}. Количество "хороших" путей гарантированно не превышает \textbf{10^9}.
Напишите программу, находящую значение максимально возможной суммы и количество "хороших" путей.
\InputFile
Первая строка содержит три целых числа \textbf{M }(\textbf{2 }≤ \textbf{M }≤ \textbf{200}), \textbf{N }(\textbf{2 }≤ \textbf{N }≤ \textbf{200}) и \textbf{K }(\textbf{0 }≤ \textbf{K }≤ \textbf{200}). Каждая из последующих \textbf{M }строк содержит \textbf{N }чисел, записанных в соответствующих клеточках.
\OutputFile
Первая строка должна содержать максимальную возможную сумму; вторая строка - количество маршрутов, сумма чисел которых отличается от максимальной не более чем на \textbf{K}.
Input example #1
2 3 3 1 9 7 2 5 3
Output example #1
20 2