Problem F
Survive The Flood

Image from Freepik

In preparation for an apocalyptic flood, you built an underground bunker. The hatches you used to build the bunker are strong enough to withstand rainwater, but once the flood is on top of them, they will break, and the water will flow into the bunker, which is located at the ground level.

You have an $n \times m$ elevation map of the above-ground height. The flood rises at $1$ unit of elevation per second. At second $0$, water is on top of elevation $0$; at second $5$, water is on top of elevation $5$. Each square of the map tells you the elevation at that coordinate.

You also have a second $n \times m$ map of your bunker, describing its layout from a vertical perspective:

• $-1$ represents solid rock not part of the bunker

• $0$ represents a hatch that breaks when water reaches its elevation

• $1$ represents a ground-level bunker tile through which water can flow

There is only one bunker with at least one hatch in the map. Your bunker is connected, that is, any tile can be reached from any other tile. When the flood reaches a hatch at second $x$, the water rushes down and that square fills with water at second $x$. From there, the water will start flooding the bunker one square at a time. That is, the adjacent squares (up, down, left, right) fill with water at time $x+1$, and so on. The boundaries of the map are considered impermeable.

With this information, if you choose the best spot to hide in the bunker (any square marked $1$ or $0$), how long can you survive?

Input

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 500$). The next $n$ lines contain a row of $m$ integers denoting the elevation map. Each elevation value is between $0$ and $20$ inclusive. The next $n$ lines contain a row of $m$ integers denoting the bunker map. Each bunker value is $1$, $0$, or $-1$, depending on whether it’s a regular bunker tile, a hatch, or solid rock.

Output

Output a single integer, the maximum number of seconds you can survive.

Explanation of Sample Input 1

The following images illustrate the elevation and bunker maps for sample input 1, along with a timeline of how the bunker is flooded.

4 4
1 3 2 0
1 3 3 2
1 2 3 1
0 1 2 1
1 -1 1 -1
1 1 0 1
1 -1 1 -1
0 -1 1 -1

5