This page is still under construction.

Parts of this page are still being built. What you see may change.

Reservoir

Interview

Time limit1sMemory limit128 MB

Summary
Raise water from the pump across edge-adjacent cells of bounded height to the highest level that floods no tree, and report the flooded count.
Level

Medium6 of 10

Topics
Shortest path, Heap, Graph
Solved
No attempts yet

Problem

Farmer Jozef wants to build a fish pond in a rectangular hollow on his land. He puts a pump at the lowest point of the hollow and fills it with water. Fruit trees grow on some cells, and he does not want any tree to end up under water. He will choose how much water to pump so that no fruit tree is flooded while the pond is as large as possible.

The land is a grid of N×MN \times M unit cells. The pump can raise the water to any level you like. A cell is covered by water when it is connected to the pump through a path of edge-adjacent cells whose heights are all at most the water level (water flows only across shared edges, never across a shared corner). The pond is the set of covered cells.

Choose the water level so that no cell holding a fruit tree is covered and the number of covered cells is as large as possible. How large can the pond be?

Input

The first line contains two integers NN and MM (1≤N,M≤10001 \le N, M \le 1000): the number of rows and columns of the plot.

Each of the next NN lines contains MM integers, each with absolute value at most 1000010000, describing the cells row by row. The absolute value of a number is the terrain height of that cell. A negative number marks a cell where a fruit tree grows. The single 00 marks the pump; it appears exactly once and sits at the lowest point. Water spreads only between cells that share an edge.

Output

Print one integer: the largest possible area of the pond (the number of covered cells).

Examples2

  1. Example 1

    Input
    4 4
    2 3 2 -4
    -1 4 0 1
    4 1 2 2
    2 3 2 -4
    
    Expected output
    7
    
  2. Example 2

    Input
    2 2
    3 5
    0 2
    
    Expected output
    4