The Kingdom of Altis consists of an N \times M grid representing a vast ocean. In this grid, a cell marked 1 represents an island tile, and a cell marked 0 represents a water tile.
Two island tiles are considered connected if they share an edge (horizontally or vertically). An island is defined as a maximal group of island tiles such that any tile in the group can reach any other tile in the same group by moving only between connected island tiles.
The King wants to connect all existing islands so that it is possible to travel from any island tile to any other island tile in the grid. To achieve this, you can transform water tiles into island tiles.
Your task is to find the minimum number of water tiles that must be changed into island tiles to make the entire archipelago connected.
It is guaranteed that number of islands in the input is at most 10 (K \le 10).
Input
The first line contains two integers, N and M (1 \leq N, M \leq 30), representing the dimensions of the grid.
The next N lines each contain a string of M characters (either 0 or 1), representing the grid. It is guaranteed that at least one 1 exists on the grid.
Output
Print a single integer: the minimum number of water tiles that need to be changed to 1 to connect all islands.
Examples
| standard input | standard output |
|---|
| 3 3
101
000
101
| 3
|