Районно-городские командные соревнования

Ваша компания продает роботов, которые могут подбирать мусор с полей после спортивных мероприятий и концертов. Прежде чем робот назначается на работу, поле фотографируется с воздуха и на фотографию наносится сетка. Каждая клетка сетки, содержащая мусор, помечается. Все роботы начинают свою работу с верхнего левого угла и заканчивают движение в нижнем правом углу. Робот может двигаться только в двух направлениях: вправо и вниз. При прохождении робота по клетке, содержащей мусор, он этот мусор будет собирать. После того, как робот достигнет правого нижнего угла, он не может быть перенаправлен или повторно использован. Так как ваши затраты прямо пропорциональны количеству роботов, задействованных в работе, вы заинтересованы в нахождении минимального количества роботов, которые смогут очистить данное поле. Например, рассмотрим карту поля, показанную на рисунке 1, с пронумерованными строками и столбцами. Клетки, содержащие мусор, помечены буквой 'G'. По этой схеме роботы будут начинать работу с позиции 1,1 и заканчивать в позиции 6,7.

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

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

Во входном файле содержится одна или более карт поля, за которой следует строка, содержащая -1 -1, что означает конец входных данных. Карта поля состоит из одной или более строк, каждая строка содержит одну клетку, где содержится мусор. За картой поля следует строка, содержащая 0 0, означающая конец карты. Каждое расположение мусора состоит из двух целых чисел: номер строки и столбца, разделенные единственным пробелом. Строки и столбцы пронумерованы, как показано на рис. 1. Расположения мусора будут заданы в отсортированном по строкам порядке. Ни одна карта не может быть больше, чем 24 строки и 24 столбца. В примере входного файла, показанном ниже, содержится две карты. Первая из них – карта поля с рис. 1.

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

1 2
1 4
2 4
2 6
4 4
4 7
6 6
0 0
1 1
2 2
4 4
0 0
-1 -1

2
1