Reservoir

You're given an elevation map — a 2D grid of non-negative integers where each cell's value is its height. After heavy rain, water collects in the valleys. Compute the total volume of water trapped on the map.

Water flows freely off the boundary of the grid (cells on the edge cannot hold any water themselves). A cell traps water up to the lowest barrier surrounding it.

Input

Line 1: two integers rows cols (1 ≤ rows, cols ≤ 250). Next rows lines: cols space-separated non-negative integers each — the heights.

Output

A single integer: the total water volume trapped on the map.

Example

Input:

3 6
3 3 3 3 3 3
3 0 0 0 0 3
3 3 3 3 3 3

Output:

12

The interior row of zeros is fully enclosed by walls of height 3, holding 4 cells × 3 height = 12 units.

Notes

• The 1D version of this problem (a single row of heights) has a classic solution: scan left-to-right and right-to-left, then for each cell compute min(max_left, max_right) - height. A common starting point is to apply that idea row by row to handle the 2D case.

Scoring

Your solution is evaluated against 10 test cases worth 10 points each (100 total).