Вам дана таблица из \(n\) строк и \(m\) столбцов, в каждой клетке которой записано число \(0\) или число \(1\).
Уголком будем называть любой квадратик \(2 \times 2\) без одной угловой клетки. Вы хотите добиться того, что в таблице не останется ни одной единицы. За одну операцию вы можете выбрать любой уголок, который содержит хотя бы одну \(1\), и заменить все числа в уголке на нули.
Вам очень нравится ваша таблица, поэтому вы хотите определить, какое максимальное количество операций вы можете сделать перед тем, как в таблице останутся лишь нули.
Выходные данные
Для каждого набора входных данных выведите единственное число — искомое максимальное количество операций.
Примечание
В первом тестовом случае одним из возможных способов оптимально выполнить операции является следующий (жирным шрифтом выделяется треугольник, на котором была выполнена операция):
- Матрица до выполнения каких либо операций:
- Матрица после выполнения \(1\) операции:
- Матрица после выполнения \(2\) операций:
- Матрица после выполнения \(3\) операций:
- Матрица после выполнения \(4\) операций:
- Матрица после выполнения \(5\) операций:
- Матрица после выполнения \(6\) операций:
- Матрица после выполнения \(7\) операций:
- Матрица после выполнения \(8\) операций:
В третьем тестовом случае из примера мы не можем выполнить ни одной операции, так как в изначальной таблице нет единиц.
В четвертом тестовом случае из примера вне зависимости от выбора первого уголка у нас всегда останется единственная единичка. Поэтому всего мы применим \(2\) операции.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
4 3
101
111
011
110
3 4
1110
0111
0111
2 2
00
00
2 2
11
11
|
8
9
0
2
|