Many engineering structures are constructed using triangles. Why is this?

The simple answer is that triangles are stable. A triangle has three sides and, if these are fixed in length, there is only one configuration they can be in. There is no flexibility or freedom. On the other hand, a quadrilateral has more degrees of freedom. Without changing any of the lengths of the sides the shape can be deformed.

Triangles help to keep structures rigid. So, to make a square rigid, we can use a cross section sub-dividing it into two triangles as shown in the figure.

In this problem we are interested to know if a given grid structure is rigid or not. A grid structure is rigid if no square can be deformed. For instance the following grid structure is not rigid as it can be deformed while maintaining the lengths of all non-crossed squares and the integrity of the crossed squares.

By adding a cross section on the lower left square, we obtain a rigid structure.

Given a grid with some cross sections, determine what is the minimum number of cross sections that must be added so that it becomes rigid.

Input

The first line contains two integers \(r\) and \(c\) giving the number of rows and columns of the grid structure. Then follow \(r\) lines each containing a binary string \(s_i\) of length \(c\) such that \(s_{ij} = 1\) if and only if square at row \(i\) and column \(j\) is braced.

Constraints

• \(1 \leq r, c \leq 1000\).

Output

A single line with a non-negative integer giving the minimum number of cross sections that must be added in order to make the structure rigid.

Sample Test Cases

Sample input 1

Sample output 1

Sample input 2

Sample output 2