The swimming pool owner

Interview

Time limit2sMemory limit128 MB

Summary

Given an N by M grid of heights, compute how much water the terrain traps, where each cell's water level is the lowest possible maximum height along any path to the border.

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

Problem

Suhyeong wants to start a swimming pool business. He decided to leave the mountain untouched and use the terrain as it is, so he neither digs nor piles up any ground. He only lets water collect where the terrain already holds it.

The ground is given as an $N \times M$ grid, and each cell carries the ground height at that spot. Water flows between cells that share an edge, and water that runs off the outside of the grid is not retained. When the terrain holds as much water as it can, the water level of a cell is defined like this. Choose a path that leaves the cell and reaches the outside of the grid, and take the largest cell height along that path. The smallest such value over all possible paths is the water level of that cell. The amount of water in the cell is its water level minus its ground height.

Given the ground heights, write a program that prints the total amount of water the terrain holds when it is filled as much as possible.

Input

The first line contains $N$ and $M$ , separated by a space. ( $1 \le N, M \le 100$ )

Each of the next $N$ lines contains $M$ integers separated by spaces. The $j$ -th integer on the $i$ -th line, $H_{i,j}$ , is the ground height of that cell. ( $0 \le H_{i,j} \le 10000$ )

Output

Print the total amount of water on the first line.

Examples3

Example 1

Input

Expected output

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