E. Bridge Construction
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A certain tropical republic is an archipelago consisting of several (at least two) islands. The map of the archipelago is represented by an $$$n \times m$$$ matrix, where the symbol '1' means land and the digit '0' means water. Any two adjacent cells with the symbol '1' belong to the same island.

The newly elected president of the republic promised to connect all the islands with bridges during the election campaign. Now the promise needs to be fulfilled, but there is not much money in the country. Therefore, he decided to start with the construction of the smallest bridge. Determine the smallest number of cells that need to be changed from '0' to '1' so that any two islands (or more) are connected.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1\le n, m \le 10^6$$$, $$$n \cdot m \le 10^6$$$).

The next $$$n$$$ lines contain $$$m$$$ characters '0' or '1' without spaces. It is guaranteed that there are at least two connected regions of unit cells in the matrix.

Output

Output a single integer — the answer.

Examples
Input
3 3
101
010
101
Output
1
Input
2 3
100
001
Output
2