Problem description

W tegorocznej Bitockiej Olimpiadzie Zimowej wprowadzono nową kategorię sportową: narciarstwo przełajowe. Wyznaczony został górski teren, którego można przedstawić jako siatka N × M pól, każde z nich położone na pewnej wysokości. Zadaniem uczestników będzie manewrować na stoku, zaczynając w dowolnym punkcie i przemieszczając się w dowolnym z czterech kierunków, północy, południa, wschodu i zachodu. Celem zawodów jest odwiedzić pewien zbiór pól na stoku wyznaczony przez organizatorów.

Organizatorzy olimpiady chcieliby określić trudność zawodów. Stok ma trudność K, jeżeli istnieje możliwość przejazdu między każdą parą wyznaczonych pól stoku, przejeżdżając jedynie między sąsiednimi polami o maksymalnej różnicy wysokości K. Organizatorzy szukają minimalnego K spełniającego tę wartość. Znalezienie tej wartości przypadło Tobie!

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby N oraz M oznaczające wymiary stoku. W następnych N wierszach następuje opis stoku. Każdy wiersz składa się z M liczb. j-ta Liczba w i-tym wierszu to w_i, j i oznacza wysokość pola (i,j). Następnie, w następnych N wierszach następuje opis wyznaczonych przez organizatorów pól do odwiedzenia. Każdy wiersz składa się z M liczb, j-ta liczba w i-tym wierszu, x_i, j, jest równa 1, gdy pole (i,j) jest wyznaczone do odwiedzenia oraz 0 w przeciwnym przypadku.

Wyjście

W jedynym wierszu wyjścia należy wypisać jedną liczbę całkowitą oznaczającą minimalne K takie, że między każdą parą wyznaczonych pól można przejechać zjeżdżając jedynie między polami o różnicy wysokości co najwyżej K.

Ograniczenia

1 ≤ N ⋅ M ≤ 200 000, 0 ≤ w_i, j ≤ 10⁹, x_i, j ∈ {0, 1} dla 1 ≤ i ≤ N, 1 ≤ j ≤ M. Możesz założyć, że co najmniej jedno pole zostało wyznaczone, tj. że istnieją takie i, j, że x_i, j = 1.

Podzadania

Przykład

3 5
16 6 0 10 13
9 15 17 10 12
4 0 4 24 15
1 1 0 0 1
0 0 0 0 0
0 0 0 1 0

9