2015. október
2015. október
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

Adott egy hegység térképe, pontosabban egy N × M-es táblázat az egyes koordináták magasságával, melyek egyike sem nagyobb, mint 109. Továbbá adott néhány nagyon szép hely a hegységben. Azt szeretnénk eldönteni, hogy legalább mennyire nehéz az a túra, amely minden szép helyet meglátogat valamelyik szép helyről kiindulva. Azaz formálisan a legkisebb C számot szeretnénk meghatározni, hogy bármelyik szép helyről bármelyik másikra el lehessen jutni úgy, hogy közben a térképen egy mezőről mindig egy másik olyan élszomszédos mezőre lépünk, melyek szintkülönbsége legföljebb C.

Input

A program olvassa be a standard input első sorából N-et és M-et, a térkép sorainak és oszlopainak számát (1 ≤ N, M ≤ 800), majd a következő N sorból soronként M db egészet: a magasságokat. Az utána következő N sorból is soronként M db egészet, melyek 0-k, vagy 1-ek lehetnek: 0, ha nem szép a hely, és 1, ha szép.

Output

A program írja a standard output első és egyetlen sorába a lehető legkisebb megfelelő C számot.

Example

Input
3 5
20 21 18 99 5
19 22 20 16 26
18 17 40 60 80
1 0 0 0 1
0 0 0 0 0
0 0 0 0 1
Output
21

Információk
Azonosító:
s101
Cím:
2015. október
Időlimit:
3000 ms
Memórialimit:
64 MiB
Típus:
batch

Megoldás beküldése
Beküldéshez lépj be vagy regisztrálj!

Mellékletek