Trapping Rain Water in a City

You are given a 2D grid representing the elevation map of a city. Each cell has a non-negative height value. When it rains, water gets trapped in the dips of the terrain. The water cannot flow out from the boundary cells.

Your task is to compute the total amount of water that can be trapped after the rain.

More formally, given an elevation matrix \( H \) of dimensions \( m \times n \), you need to calculate the water volume accumulated. Let \( H[i][j] \) denote the height at cell \( (i, j) \). The water level at each cell is determined by the minimum of the maximum heights from its adjacent border cells, and the water stored at that cell is \( \max(0, W - H[i][j]) \), where \( W \) is the water level.

Note: If the grid is empty or either \( m \) or \( n \) equals 0, the result is 0.

inputFormat

The first line contains two integers ( m ) and ( n ) representing the number of rows and columns of the height map respectively. This is followed by ( m ) lines each containing ( n ) space-separated integers, where each integer represents the height at that cell.

outputFormat

Output a single integer which is the total amount of water trapped after the rain.## sample

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

4