Chisam's Stepping Stone Crossing

Chisam wants to cross a square valley that is $N$ wide and $N$ tall. But the tremendous heat has dried up all the water!

The valley consists of ground and stones. The whole ground is made of $1\times1$ cells, and a cell may contain a stone. The ground and stones in the valley are too hot to walk on. However, a cell with a stone becomes cool enough to walk on once water flows into it. Fortunately, kind students dug into the ground to create water sources for Chisam, and Chisam decided to cross the valley by stepping on stones. A water source may lie on either ground or a stone. Water spreads once a day from each cell that contains water to cells adjacent to it. Diagonal cells are not considered adjacent.

Chisam wants to travel from the starting point $(1, 1)$ to the destination $(N, N)$. Stones always lie at the starting point $(1, 1)$ and the destination $(N, N)$, and Chisam can walk on them without meeting water. Chisam's movement takes no time. Chisam can move up, down, left, right, and diagonally. Find the number of days it takes for Chisam to reach the destination $(N, N)$ as fast as possible.

The first line gives the size of the ground $N(3 \le N \le 1,000)$ and the number of water sources $W(1 \le W \le N)$.

Lines 2 through $W+1$ give the position of each water source $x$ (row), $y$ (column) $(1 \le x, y \le N)$.

From line $W+2$, $N$ lines give the map of the stream. 1 marks a cell with a stone, and 0 marks a cell with ground.

$N$, $W$, $x$, and $y$ are all positive integers.

Print the number of days it takes to reach the destination as fast as possible. If Chisam cannot reach the destination $(N, N)$, print -1.