The Carpenter

Time limit2sMemory limit128 MB

Summary

Cut two non-overlapping diagonal triangles from an n by m black-and-white board and glue them into the largest square with alternating colors.

Level: Hard8 of 10
Topics: Dynamic programming, Matrix, Prefix sum
Solved: No attempts yet

Problem

Byteasar wants to play a game of checkers, but he cannot find his chessboard. All he found is a wooden board of size $n \times m$ , divided into $nm$ equally sized square fields. Each field is painted white or black, and the colours are not necessarily arranged in a proper chessboard pattern.

Byteasar decided to put his carpentry experience to use and cut a chessboard out of the wood with a saw. A chessboard here is a square built from square fields in which every two fields sharing a side have different colours. A $1 \times 1$ square has no pair of fields sharing a side, so it counts as a chessboard too.

The board might not contain a square of the size he wants. So he decided to cut out two triangular pieces and glue them together into a chessboard. The two pieces must not overlap, but he may turn them around in any way after cutting them out.

A piece is cut like this. Pick a square area of the board with side $k$ fields and saw along one of its diagonals. The two legs of the resulting triangle run along field boundaries and the hypotenuse runs through field corners, so every field the hypotenuse crosses is split into two halves. Gluing two such pieces along their hypotenuses gives a $k \times k$ square. Two halves that meet on the hypotenuse become one field of the finished square, so they must have the same colour.

The two pieces must not overlap. Two different pieces each taking one half of a field the saw passed through does not count as overlapping. The figure below shows a board of size $4 \times 5$ and two triangles that glue together into a chessboard of size $3 \times 3$ .

Find the largest chessboard size Byteasar can obtain this way.

Input

The first line contains two integers $n$ and $m$ , the size of the board ( $1 \le n, m \le 1000$ ).

Each of the next $n$ lines contains $m$ integers. The $j$ -th number in the $i$ -th line is the colour of the field where row $i$ meets column $j$ , where $0$ is a white field and $1$ is a black field ( $1 \le i \le n$ , $1 \le j \le m$ ).

Output

Print one integer, the number of fields along one side of the largest chessboard that can be made by cutting out two triangular pieces and gluing them together.

Examples2

Example 1

Input

Expected output

Example 2
Input
```
3 3
1 1 1
1 1 0
0 1 0
```
Expected output
```
2
```