Задача B. Сборщики мусора.

Задачу добавил: alef

Успешно сдано решений: 8

К очистке городского пляжа от мусора, скопившегося после половодья, привлекли M волонтеров-школьников. А чтобы работать им было веселее, организаторы решили добавить к работе немного игры. На пляже нарисовали прямоугольную сетку (из M столбцов и N строк), а волонтерам выдали по N флажков и объявили следующие правила. Сначала каждый волонтер стоит в первой клетке «своего» столбца. В клетках сетки содержится различное количество единиц мусора (от 0 до G), а на сбор одной единицы мусора у волонтера уходит одна единица времени (предполагается, что мусор остался только мелкий, и не существует таких «единиц мусора», которые помещаются одновременно более чем в одной клетке).

Из своей «текущей позиции» волонтер может пойти собирать мусор либо «вперед» (в следующей клетке текущего столбца), либо «вперед и влево» (в клетке столбца слева, соседствующей со следующей клеткой текущего столбца), либо «вперед и вправо» (в клетке столбца справа, соседствующей со следующей клеткой текущего столбца). Разумеется, находясь в крайнем левом столбце, нельзя пойти «вперед и влево», равно как нельзя пойти «вперед и вправо», находясь в крайнем правом столбце. В каждой клетке, в которой волонтер убрал мусор, он оставляет один из своих флажков.

Если волонтер пойдет через клетку, в которой уже находится флажок другого волонтера или же собственно другой волонтер, уже собирающий мусор, то он «получит» G+1 штрафную единицу времени (его немедленно привлекут поработать на погрузке мусора в течение этого времени, после чего он сможет вернуться и продолжить собирать мусор). Свой флажок он там оставить не может.

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

В случае, если минимальное время выполнения работы на нескольких путях одинаково, наибольшим преимуществом наделено направление «вниз» (см. рис.), затем «вниз и влево» и, наконец, «вниз и вправо». Если два или более волонтеров одновременно хотят занять одну клетку, то наибольшее преимущество имеет тот, кто стартовал со столбца с меньшим номером.

Ваша задача — определить, какое количество клеток и какое количество мусора останется неубранным при оптимальных действиях всех участников и через какое время закончится уборка.

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

Первая строка — целые числа M, N, G (1 <= M, N, G <= 100) через пробел (M — количество волонтеров и столбцов в сетке, N — количество строк в сетке, G — максимально возможное количество единиц мусора в клетке).

Каждая из следующих N строк содержит по M целых чисел (от 0 до G) через пробел, задающих количество единиц мусора в клетках.

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

Первая строка — целое число — количество клеток, которые останутся неубранными

Вторая строка — целое число — количество единиц мусора, оставшегося неубранным

Третья строка — целое число — количество единиц времени, спустя которое закончится уборка (т.е. последний из волонтеров соберет мусор в той клетке последнего ряда, в которой он окажется).

Пример входного файла — 1

5 5 11

10 10 10 10 10

10 10 10 11 10

10 10 10 10 0

Пример выходного файла — 1

Пояснение к примеру 1.

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