Drain Byteburg Minimally

Byteburg, the capital of Byteotia, is completely flooded after heavy rains. King Byteasar has decided to use pumps to drain the flooded area. You are given a map of the city and its surrounding valley in the shape of a \(m \times n\) grid. Each cell in the grid contains:

• Its height above sea level (an integer).
• A flag indicating whether it is part of Byteburg (1) or not (0).

The entire area is under water and is surrounded by mountains, so water cannot flow out. A pump placed in any cell will drain that cell completely. Moreover, by the principle of communicating tubes, if water can flow from one cell to the cell with the pump then that cell will also be drained. Water flows only between cells sharing a common side and only flows from a cell to a neighboring cell if the neighbor has a strictly lower height (i.e. water flows down).

Your task is to choose a set of cells in which to place pumps so that every Byteburg cell (cells marked with 1) is drained. Find the minimum number of pumps needed.

Note: Although pumps can be placed in any cell, you do not need to drain cells that are not part of Byteburg. However, note that water may flow through non‐Byteburg cells, and such cells can serve as a corridor connecting Byteburg cells to a pump.

inputFormat

The input is read from standard input and has the following format:

 m n
 h[0][0] h[0][1] ... h[0][n-1]
 h[1][0] h[1][1] ... h[1][n-1]
 ...
 h[m-1][0] h[m-1][1] ... h[m-1][n-1]
 b[0][0] b[0][1] ... b[0][n-1]
 b[1][0] b[1][1] ... b[1][n-1]
 ...
 b[m-1][0] b[m-1][1] ... b[m-1][n-1]

Here, the first line contains two integers \(m\) and \(n\) denoting the number of rows and columns in the map. The next \(m\) lines each contain \(n\) integers (the heights). The following \(m\) lines each contain \(n\) integers, where each integer is either 1 (the cell is part of Byteburg) or 0 (it is not).

outputFormat

Output a single integer: the minimum number of pumps required to drain all Byteburg cells. The result is written to the standard output.

sample

3 3
9 6 3
5 4 2
7 1 0
1 1 0
0 1 1
1 0 1

1