595. Trapping Rain Water II

0

Hard

Given an m x n integer matrix heightMap representing the height of each unit cell in a 2D elevation map, Print the volume of water it can trap after raining.

Input Format

First line contains Number of Rows

Second line contains Number of Columns

Third line contains elements of matrix

Second line contains Number of Columns

Third line contains elements of matrix

Output Format

Print volume (Integer)

Example

Input

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

Output

4

Constraints

m == heightMap.length

n == heightMap[i].length

1 <= m, n <= 200

0 <= heightMap[i][j] <= 2 * 10

n == heightMap[i].length

1 <= m, n <= 200

0 <= heightMap[i][j] <= 2 * 10

^{4}Loading...

View Submissions

Console