Автобусные маршруты

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

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

Задача

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

Входные данные

В первой строке входного файла busways.in указаны два натуральных числа: количество горизонтальных дорог N и количество вертикальных дорог M в пригороде. Известно, что 2 ≤ N ≤ M ≤ 1000. В следующих N строках содержится по M перекрестков: число 1 обозначает важный перекресток, а число 0 — неважный.

Выходные данные

Выходной файл busways.out должен содержать одно неотрицательное целое число — минимальное количество маршрутов, необходимых для покрытия всех важных перекрестков вдоль кратчайших путей от левого нижнего до правого верхнего перекрестка.

Примеры

Оценивание