EMILABC - Big Pyramid

no tags 

Archeologists have discovered an ancient manuscript describing a big pyramid. The pyramid is built of cubical stone blocks as shown in the picture. There are N horisontal levels in the pyramid. The topmost level consists of a single block, and the base level is a square of 2*N-1×2*N-1 blocks. The archeologists learned from the manuscript the size of a stone block and the orientation the pyramid. However, they do not know the size and the exact location of the pyramid.

There are many hills in the land where the pyramid is believed to be located. The archeologists think that one of the hills is actually the pyramid covered with sand. To check that hypothesis, they produced an elevation map of the land. The land was divided into a grid of H×W cells. The size of a cell is the same as the size of a stone block face. For each cell they measured its height and calculated how many stone blocks can be underneath the surface of the cell.

Now the archeologists give you the elevation map and ask to compute the largest possible pyramid size, assuming that the pyramid base sides are parallel to the grid lines.

Input

The first line of the input contains two integers H and W (0 < H, W ≤ 200). Each of the subsequent H lines contains W integers. Each integer is non-negative and less than 201.

Output

One interger - the number of levels in the larget possible pyramid.

Example

Input:

5 6
0 0 0 0 0 0
0 1 0 0 0 0
0 0 1 1 1 1
0 0 1 1 2 1
0 0 1 1 1 1

Output:

2

hide comments
nadstratosfer: 2017-11-13 10:10:46

Thrown a lot out of the base O((nm)^2) concept and got AC with Python in 0.03s although my code does feature a stage where some operations are repeated. Glad I don't *have* to optimize to get AC though, it cost me 4 hours to produce my solution and it would be heartbreaking if TLE turned this work to waste. This is the most satisfying solution out of 392 problems I've solved so far here on SPOJ, had a lot of fun getting from a rough idea to a somewhat elegant program.

[Rampage] Blue.Mary: 2016-01-20 08:28:39

Weak test cases, O((nm)^2) accepted in 0.00.(Although to the worst test case which I can ever imaged my program can pass in 1 second.)

Ehor Nechiporenko: 2013-01-25 14:55:34

Hey, Image is lost! Could someone to restore it?

:D: 2012-08-22 12:46:46

Well, yes, of course.

Amit Gupta: 2012-08-18 08:15:39

Does the pyramid have to be fully contained inside the grid?


Added by:Azat Taryhchiyev
Date:2011-02-04
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ASM32-GCC MAWK BC C-CLANG C++ 4.3.2 CPP CPP14 CPP14-CLANG C99 COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JAVA JS-MONKEY KTLN NIM NODEJS OBJC OBJC-CLANG OCT PAS-GPC PAS-FPC PICO PROLOG PYPY PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:International Sebat Institutions