Гридландия была затронута наводнением, и теперь в ней придётся восстанавливать все города. Гридландию можно описать матрицей размера $$$n \times m$$$.

Изначально все её города находятся в экономическом кризисе. Правительство может выбрать определённые города и восстановить их. Кроме того, любой разрушенный город, у которого есть хотя бы один соседний по вертикали восстановленный город и хотя бы один соседний по горизонтали восстановленный город, может попросить помощи у них и стать восстановленным без помощи правительства. Формально, разрушенный город, находящийся на позиции $$$(i, j)$$$, может быть восстановлен, если оба из следующих условий выполнены:

• Хотя бы один из городов на позициях $$$(i + 1, j)$$$ и $$$(i - 1, j)$$$ восстановлен;
• Хотя бы один из городов на позициях $$$(i, j + 1)$$$ и $$$(i, j - 1)$$$ восстановлен.

Если город находится на границе матрицы и имеет только один соседний по горизонтали или по вертикали город, то мы рассматриваем только этот город.

Иллюстрация двух возможных способов восстановления городов при помощи соседних. Белые ячейки — разрушенные города, желтые ячейки — изначально восстановленные города (либо правительством, либо при помощи соседних), и оранжевые ячейки — восстановленные города при помощи соседних.

Правительство хочет знать минимальное количество городов, которые ему нужно восстановить, чтобы через некоторое время все города были восстановлены.