Под дворцом царя Миноса размером $$$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 101 0 0 0 0 0 0 0 0 1
0
2 50 0 0 0 00 1 1 1 0
2