Майже максимум
Маємо прямокутну таблицю розміром N рядків на M стовпців, заповнену натуральними числами, що не перевищують 1000. Потрібно пройти з лівого верхнього кута в правий нижній, переміщуючись на одну клітинку вправо або вниз. Під час переміщення рахуємо суму чисел у пройдених клітинках. Наша мета – знайти максимальну можливу суму, яку можна зібрати таким способом.
Але це ще не все. Назвемо шлях майже максимальним, якщо сума зібраних чисел відрізняється від максимальної суми не більше, ніж на K (0 <= K <= 100). Звісно, йдеться про шляхи з лівого верхнього кута в правий нижній з кроками вправо або вниз. Потрібно визначити кількість майже максимальних шляхів. Їх може бути досить багато, тому треба виводити не саму кількість майже максимальних шляхів, а залишок від ділення цієї кількості на 20102010.
Вхідні дані
У першому рядку знаходяться три натуральні числа: N (2 <= N <= 300), M (2 <= M <= 300) і K (0 <= K <= 100). Кожен з наступних N рядків містить M натуральних чисел, що не перевищують 1000 – вміст таблиці. Сусідні числа в рядку розділяються одним пробілом.
Вихідні дані
У першому рядку має знаходитися одне натуральне число – найбільша сума, яку можна набрати, рухаючись за правилами з лівого верхнього кута в правий нижній. У другому (і останньому) рядку має знаходитися одне ціле число – залишок від ділення кількості майже максимальних шляхів на 20102010.