Ковролин для минотавра
ограничение по времени на тест
8 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Что за свинья прошла здесь — корова, что ли?

Под дворцом царя Миноса размером $$$N \times M$$$ построен одноэтажный лабиринт размером $$$N \times M \times 1$$$. Некоторые из кубов $$$1 \times 1 \times 1$$$ в этом лабиринте пустые, а некоторые — гранитные (сквозь них ходить нельзя). Количество пустых кубов в лабиринте $$$S$$$. Минотавр, гуляя в этом лабиринте только по пустым кубам, может дойти от любого пустого куба до любого другого пустого.

К сожалению, минотавр очень громко топает, поэтому выбранная им жертва успевает испугаться и убежать. Для того, чтобы этого избежать, фирма «Минос, минотавр and Co» закупила ковролин, которым собирается застелить пол пустых кубов, чтобы минотавр мог подбираться к жертве бесшумно. Рулон ковролина имеет размеры $$$1 \times S$$$. Рабочие хотят застелить пол лабиринта, сделав как можно меньше разрезов ковролина (разрезы разрешается делать только параллельно стороне рулона, имеющей длину $$$1$$$).

Напишите программу, вычисляющую это минимальное число разрезов.

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

В первой строке задается два целых числа $$$N$$$ и $$$M$$$ $$$(1 \leqslant N \leqslant 10; 1 \leqslant M \leqslant 10)$$$ — размеры лабиринта.

Далее идет $$$N$$$ строк по $$$M$$$ целых чисел в каждой, задающих лабиринт. Каждое из этих чисел равно $$$0$$$ или $$$1$$$ — $$$0$$$ означает пустой куб, а $$$1$$$ — гранитный.

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

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

Примеры

Входные данные
1 10
1 0 0 0 0 0 0 0 0 1
Выходные данные
0
Входные данные
2 5
0 0 0 0 0
0 1 1 1 0
Выходные данные
2