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