Trapping Rainwater II

You are given a 2D matrix representing an elevation map where each cell contains a non-negative integer denoting the height of the terrain at that point. When it rains, water may be trapped in the low-lying areas that are surrounded by higher terrain. Your task is to compute the total volume of water that can be trapped after raining over the entire elevation map.

More formally, given a matrix heightMap of dimensions \(n \times m\), determine the sum of water units that can be stored in the depressions. The water in each cell is determined by the minimum of the heights of the surrounding boundaries (including edge cells) minus the height at that cell, with the constraint that water cannot be negative.

Note: The boundaries of the map cannot trap water by themselves.

Input/Output

inputFormat

The first line of input contains two integers \(n\) and \(m\) representing the number of rows and columns respectively.

Each of the next \(n\) lines contains \(m\) space-separated integers representing the height map.

outputFormat

Output a single integer representing the total volume of water trapped.

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

4