Почти максимум
Имеется прямоугольная таблица размером N строк на M столбцов, заполненная натуральными числами, не превосходящими 1000 . Нужно пройти из левого верхнего угла в правый нижний, перемещаясь на одну клетку влево или вниз. При перемещении считаем сумму чисел в пройденных клетках. Наша цель – найти максимальную возможную сумму, которую можно собрать таким способом.
Но это ещё не всё. Назовём путь почти максимальным, если сумма собранных чисел отличается от максимальной суммы не более, чем на K (0 <= K <= 100). Конечно, речь идёт о путях из левого верхнего угла в правый нижний с шагами вправо или вниз. Требуется определить количество почти максимальных путей. Их может быть довольно много, поэтому надо выводить не само количество почти максимальных путей, а остаток от деления этого количества на 20102010.
####Входные данные.В первой строке находятся три натуральных числа: N (2 <= N <= 300), M (2 <= M <= 300) и K (0<= K <= 100). Каждая из следующих N строк содержит M натуральных чисел, не превосходящих 1000 – содержимое таблицы. Соседние числа в строке разделяются одним пробелом.
####Выходные данные.В первой строке должно находиться одно натуральное число – наибольшая сумма, которую можно набрать, двигаясь по правилам из левого верхнего угла в правый нижний. Во второй (и последней) строке должно находиться одно целое число – остаток от деления количества почти максимальных путей на 20102010.