Trapping Rain Water II

You are given a 2D grid of dimensions n x m where each cell contains an integer representing its elevation. When it rains, water may be trapped in the low lying areas. The amount of water that can be trapped at each cell is given by the difference between the water level and the cell's elevation, but water cannot be held above the boundary of the grid. More formally, if the water level on a cell is w and the elevation is h, then the water trapped in that cell is \(\max(0, w-h)\). Your task is to compute the total volume of water that can be trapped over the entire grid after the rain.

Note: The water can flow into neighboring cells (up, down, left, right) and the boundary of the grid cannot trap water.

inputFormat

The input is given via standard input (stdin) in the following format:

n m
row1
row2
...
rown

Here, n and m are integers representing the number of rows and columns respectively. Each of the next n lines contains m space-separated integers denoting the elevation values of that row. If n or m is 0, the grid is considered empty.

outputFormat

Output a single integer to standard output (stdout), representing the total volume of trapped water.

3 6
1 4 3 1 3 2
3 2 1 3 2 4
2 3 3 2 3 1

4