Задача №78. Прямоугольники

Дан прямоугольник N x M, состоящий из квадратиков 1 x 1. Некоторые квадратики вырезали. Надо найти наименьшее количество прямоугольников, на которое можно разрезать оставшуюся фигуру.

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

В первой строке входных данных заданы числа N и M, (1 ≤  N, M ≤ 10). Далее следует N строк. В (i+1)-ой содержится M чисел; j-е число равно 1, если клетку на i-й строке и в j-м столбце вырезали из доски, 0 – если оставили.

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

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

Примеры
Входные данные
2 2 
0 0
1 0
Выходные данные
2
Сдать: для сдачи задач необходимо войти в систему