0005. Грибы

Имя входного файла:	mushroom.in
Имя выходного файла:	mushroom.out
Ограничение по времени:	6 s
Ограничение по памяти:	128 megabytes

Шерлок Холмс и доктор Ватсон отправились в лес собирать грибы. Лес можно представить в виде прямоугольной решетки размерами NxM шагов, в каждой клетке которой растёт некоторое количество подберёзовиков и подосиновиков. Мистер Холмс собирает только подберёзовики, а мистер Ватсон - подосиновики.

Как истинные джентльмены, они предпочитают двигаться строго на юг или на восток, а как настоящие друзья - не отходят друг от друга на расстояние, больше чем на K шагов. Они могут сделать очередной ход одновременно, но при этом один может подождать другого.

Свой путь джентльмены начинают в северо-западном углу леса (левой верхней клетке), а закончить должны в юго-восточном (правой нижней). Требуется определить, какое максимальное количество грибов могут собрать сыщик и его компаньон.

Формат входного файла

Первая строка входного файла содержит три числа N, M и K (1 ≤ N, M ≤ 200, 0 ≤ K ≤ 10) - размеры леса и ограничение на максимальное расстояние в шагах между ними. Далее следуют N строк по M чисел A_ij - количество подберезовиков в клетке (i, j). Следующие N строк содержат по M чисел B_ij - количество подосиновиков в клетке (i, j). Все числа разделяются пробелами.

Формат выходного файла

Выведите максимальное количество грибов, которые вместе могут собрать Шерлок Холмс и доктор Ватсон.

Пример:

mushroom.in	mushroom.out
2 2 2 1 1 0 1 1 0 1 1	6
2 2 0 1 1 0 1 1 0 1 1	5
4 4 2 10 10 10 10 0 0 0 10 0 0 0 10 0 0 0 10 10 0 0 0 10 0 0 0 10 0 0 0 10 10 10 10	110

Источник: Командное школьное первенство Республики Карелия по программированию, май 2008.

Обсудить       Отправить решение



Версия для печати