Maximum Prize Square

You are given a grid of size \(N \times M\). Each cell in the grid may or may not contain a prize. The grid is represented by integers: 0 indicates no prize, and 1 indicates a prize. Your task is to choose a square subgrid (of size \(s \times s\), where \(1 \le s \le \min(N, M)\)) that meets the following condition:

• One of its two main diagonals (either the primary diagonal or the secondary diagonal) has all cells containing a prize (i.e., each cell in that diagonal is 1).
• All other cells in the chosen square subgrid (i.e. the cells not on that diagonal) have no prize (i.e., are 0).

If such a square is found, you will obtain all the prizes within that square (which is exactly \(s\) prizes). Your goal is to maximize the number of prizes obtained, i.e. to maximize \(s\) among all valid square subgrids. If no valid square subgrid exists, output 0.

Note: A square subgrid of size 1 is valid if its single cell is 1.

inputFormat

The first line contains two integers \(N\) and \(M\) denoting the number of rows and columns in the grid, respectively.

Each of the next \(N\) lines contains \(M\) space-separated integers (each either 0 or 1) representing the grid.

outputFormat

Output a single integer, the maximum number of prizes that can be obtained (i.e. the maximum valid square size \(s\)). If no valid square is found, output 0.

sample

3 3
1 0 0
0 1 0
0 0 1

3