Майже максимум#10003

Майже максимум

1 секунда

64 мегабайти

Легка

Маємо прямокутну таблицю розміром $N$ рядків на $M$ стовпців, заповнену натуральними числами, що не перевищують $1000$ . Потрібно пройти з лівого верхнього кута в правий нижній, переміщуючись на одну клітинку вправо або вниз. Під час переміщення рахуємо суму чисел у пройдених клітинках. Наша мета – знайти максимальну можливу суму, яку можна зібрати таким способом.

Але це ще не все. Назвемо шлях майже максимальним, якщо сума зібраних чисел відрізняється від максимальної суми не більше, ніж на $K$ ( $0 \leq K \leq 100$ 0 \le K \le 100). Звісно, йдеться про шляхи з лівого верхнього кута в правий нижній з кроками вправо або вниз. Потрібно визначити кількість майже максимальних шляхів. Їх може бути досить багато, тому треба виводити не саму кількість майже максимальних шляхів, а залишок від ділення цієї кількості на $20102010$ .

Вхідні дані

У першому рядку знаходяться три натуральні числа: $N$ ( $2 \leq N \leq 300$ 2 \le N \le 300), $M$ ( $2 \leq M \leq 300$ 2 \le M \le 300) і $K$ ( $0 \leq K \leq 100$ 0 \le K \le 100). Кожен з наступних $N$ рядків містить $M$ натуральних чисел, що не перевищують $1000$ – вміст таблиці. Сусідні числа в рядку розділяються одним пробілом.

Вихідні дані

У першому рядку має знаходитися одне натуральне число – найбільша сума, яку можна набрати, рухаючись за правилами з лівого верхнього кута в правий нижній. У другому (і останньому) рядку має знаходитися одне ціле число – залишок від ділення кількості майже максимальних шляхів на $20102010$ .

Приклади

Приклад 1

Приклад 2