Mud Flow

In a hilly area like Los Angeles, heavy rain from a hurricane causes mud slides. Rain loosens soil and debris, which then flows downhill. Further down, the rain falling there and the water arriving from above loosen even more soil, and soon a full mud slide comes down. It can bury houses and roads and kill people in its path. Given the initial soil and the rain falling on each cell, compute the maximum amount of soil that ends up on any one cell.

The area is a rectangular grid. Each cell has a height, an initial amount of soil, an amount of rain that falls on it, and a threshold of water needed to dislodge the soil on it. Soil and rain do not change the height.

Water that reaches a cell runs downhill to an adjacent (horizontal or vertical) cell that is strictly lower. If several adjacent cells are lower, the water splits evenly among them. If no adjacent cell is lower, the water stays on the cell. If the water reaching a cell strictly exceeds its dislodging threshold, all the soil on that cell starts flowing downhill. Water counts for every cell it flows across. Once dislodged, soil splits evenly among all adjacent strictly lower cells. Moving soil keeps going until it cannot go any lower, even if the water on a cell it passes is not enough to dislodge new soil. Soil does not help dislodge other soil. Only water does.

The area is surrounded by high mountains, so no water or mud crosses its border. Compute the maximum amount of soil that ends up on any one cell of the map. Use double for all computations, not float.

1 As a general note, there is no reason not to use double in any programming contest or in any programming work. The memory saved is not worth it. Many programmers consider float an "f-word".

The first line contains K (1 ≤ K ≤ 100), the number of data sets. Each data set starts with a line containing two integers n and m (1 ≤ n, m ≤ 300), the size of the region. Four blocks follow, each with n lines of m floating point numbers. The entry in row y, column x of a block is for cell (x, y).

• Heights: $0.0 \le h_{y,x} \le 100.0$
• Soil: $0.0 \le s_{y,x} \le 100.0$
• Rain: $0.0 \le r_{y,x} \le 100.0$
• Thresholds: $0.0 \le t_{y,x} \le 100.0$

All comparisons between floating point numbers differ by either zero or at least 0.0001, so rounding is not an issue.

For each data set, print "Data Set x:" on its own line, where x is the data set number. Then print the maximum amount of soil that ends up on any one cell. Print a blank line after each data set.