Гридландия была затронута наводнением, и теперь в ней придётся восстанавливать все города. Гридландию можно описать матрицей размера \(n \times m\).
Изначально все её города находятся в экономическом кризисе. Правительство может выбрать определённые города и восстановить их. Кроме того, любой разрушенный город, у которого есть хотя бы один соседний по вертикали восстановленный город и хотя бы один соседний по горизонтали восстановленный город, может попросить помощи у них и стать восстановленным без помощи правительства. Формально, разрушенный город, находящийся на позиции \((i, j)\), может быть восстановлен, если оба из следующих условий выполнены:
- Хотя бы один из городов на позициях \((i + 1, j)\) и \((i - 1, j)\) восстановлен;
- Хотя бы один из городов на позициях \((i, j + 1)\) и \((i, j - 1)\) восстановлен.
Если город находится на границе матрицы и имеет только один соседний по горизонтали или по вертикали город, то мы рассматриваем только этот город.
Иллюстрация двух возможных способов восстановления городов при помощи соседних. Белые ячейки — разрушенные города, желтые ячейки — изначально восстановленные города (либо правительством, либо при помощи соседних), и оранжевые ячейки — восстановленные города при помощи соседних. Правительство хочет знать минимальное количество городов, которые ему нужно восстановить, чтобы через некоторое время все города были восстановлены.
Выходные данные
Для каждого набора входных данных выведите единственное целое число — минимальное количество городов, которые правительству нужно восстановить.
Примечание
В первом наборе входных данных достаточно, чтобы правительство восстановило города \((1, 2)\) и \((2, 1)\).
Во втором наборе входных данных достаточно, чтобы правительство восстановило города \((1, 4)\), \((2, 2)\), \((3, 1)\), \((3, 6)\), \((4, 3)\), \((5, 5)\), \((5, 7)\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2 2
5 7
3 2
|
2
7
3
|