Альтернативные пути

[Anuto4ka]

Задано прямоугольную таблицу размером M строк на N столбиков. В каждой клеточке записано натуральное число, не превышающее 200. Путник должен пройти по этой таблице из левого верхнего угла в правый нижний, на каждом шаге перемещаясь либо на 1 клеточку направо, либо на 1 клеточку вниз. Очевидно, таких путей много. Для каждого пути можно вычислить сумму чисел в пройденных клеточках. Среди этих сумм, очевидно, есть максимальная.
Будем снисходительными к Путнику, считая «хорошими» не только пути, на которых в точности достигается максимально возможная сумма, а еще и пути, сумма которых отличается от максимальной не более чем на K.
Количество «хороших» путей гарантированно не превышает 109.
Задание
Напишите программу GOODWAYS, находящую значение максимально возможной суммы и количества «хороших» путей.
Входные данные
Первая строка входного файла GOODWAYS.DAT содержит три целых числа M (2≤M≤200), N (2≤N≤200) и K (0≤K≤200). Каждая из последующих M строк содержит N чисел, записанных в соответствующих клеточках.
Выходные данные
Первая строка выходного файла GOODWAYS.SOL должна содержать максимальную возможную сумму; вторая строка – количество маршрутов, сумма чисел которых отличается от максимальной не более чем на K.
Пример входных и выходных данных
GOODWAYS.DAT
2 3 3
1 9 7
2 5 3

GOODWAYS.SOL
20
2

[Levsha100]

Теорию графов уже отменили? А "пожалуйста"???

[Anuto4ka]

ну пожалуйста!