치삼이의 징검다리 건너기

치삼이는 가로로 $N$, 세로로 $N$인 정사각형 모양 계곡을 지나가려고 한다. 하지만 엄청난 더위로 인해 물이 모두 말라버렸다!

계곡은 땅과 돌로 이루어져 있다. 전체 땅은 $1\times1$ 크기의 땅들로 이루어져 있고 땅에 돌이 존재할 수 있다. 그런데 계곡의 땅과 돌이 너무 뜨거워서 지나갈 수가 없다. 하지만 돌이 있는 부분은 물이 차오르면 식어서 지나갈 수 있게 된다. 다행히 마음씨 좋은 학생들이 치삼이를 위해 땅을 파서 물이 생성되는 곳을 만들어냈고 치삼이는 돌을 밟고 계곡을 지나가기로 했다. 물 생성지에는 땅이나 돌 모두 존재할 수 있다. 물은 물이 존재하는 위치에서 하루에 한 번 물과 인접한 곳으로 퍼진다. 이때, 대각선은 인접해 있다고 보지 않는다.

치삼이는 현재 시작지점 $(1, 1)$에서 도착지점 $(N, N)$까지 가려고 한다. 시작지점 $(1, 1)$과 도착지점 $(N, N)$의 위치에는 항상 돌이 존재하며 물과 만나지 않아도 치삼이가 이동할 수 있다. 치삼이가 이동하는 것에는 시간이 걸리지 않는다. 치삼이는 상, 하, 좌, 우, 대각선으로 이동할 수 있다. 이때 치삼이가 도착지점 $(N, N)$의 위치까지 가장 빠르게 도착하는 경우 며칠이 걸리는지 알아보자.

첫 번째 줄에 땅의 크기 $N(3 \le N \le 1,000)$, 물 생성지 개수 $W(1 \le W \le N)$가 주어진다.

두 번째 줄부터 $W+1$줄까지 물의 생성 위치 $x(행), y(열)$ $(1 \le x, y \le N)$가 주어진다.

$W+2$줄부터 $N$개의 줄에 냇가의 지도가 주어진다. 1은 돌이 있는 위치를 나타내고, 0은 땅이 있는 위치를 나타낸다.

$N$, $W$, $x$, $y$는 모두 양의 정수이다.

가장 빠르게 도착지점에 도착하는 일수를 출력한다. 만약 치삼이가 도착지점 $(N, N)$에 도달하지 못하는 경우 -1을 출력한다.