Balloon Party

Interview

Time limit1sMemory limit2048 MB

Summary

Given a grid of ceiling heights, find the maximum volume of helium the tent can hold without any of it spilling over the lowest edge.

Level: Medium6 of 10
Topics: Matrix, Heap, BFS
Solved: No attempts yet

Problem

The Floating Poodle Company (FPC) plans to sell balloon animals at festivals. To make the animals float, they will fill them with helium. They have run out of helium canisters, so they will store their helium below the ceilings of the party tents where they sell the balloons.

Because of environmental laws, they may not spill any helium. They must not put too much helium into any tent. If the helium level drops below any part of the edges of the ceiling, the surplus helium will blow away and contaminate the atmosphere. They ask you to calculate the maximum amount of helium they can fit inside one of the tents.

Input

One line with two integers $w$ and $l$ ( $1 \leq w \leq 1000$ , $1 \leq l \leq 1000$ ): the width and length of the tent.

Then $l$ lines follow, each with $w$ integers in the range $[1, 1000]$ . Each integer is the height above the ground of a $1 \times 1$ section of the tent ceiling. Assume that every section is completely horizontal.

Output

The maximum amount of helium that the company can fit below the ceiling of the tent.

Examples2

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

Example 2

Input

Expected output