출근

준규는 오랜만에 회사에 출근한다. 준규는 수학을 좋아해서 무엇을 하든 규칙부터 정한다. 강남역에서 내린 준규는 회사까지 이어진 보도블록을 보고 다음 규칙을 정했다.

1. 세로 블록만 밟는다. 출발은 첫 번째 행의 세로 블록 중 아무 곳에서나 할 수 있다.
2. 미리 정해 둔 이동 규칙(예를 들어 상하좌우, 체스 나이트의 이동 규칙)으로만 움직인다.
3. 첫 번째 행에서 출발해 마지막 행에 도착하면 출근에 성공한 것이다.
4. 걷는 것이 몹시 귀찮으므로 걸음 수를 최소로 한다.

위 보도블록으로 간단한 예를 들어 보자. 1번 규칙에 따라 밟을 수 있는 블록은 색칠한 세로 블록이고, 이동 규칙이 오른쪽 그림과 같다면 준규는 여러 경로 중 점선과 실선의 방법으로 출근할 수 있다. 실선은 세 걸음이 필요하지만 점선은 두 걸음이면 된다.

수학을 좋아하지만 잘하지는 못하는 준규를 위해, 준규가 만든 규칙으로 출근할 수 있는지, 할 수 있다면 최소 몇 걸음이 필요한지 출력하는 프로그램을 작성하시오.

첫째 줄에 보도블록의 세로 크기 R과 가로 크기 C가 주어진다 ($1 \le R, C \le 1000$). 다음 R개의 줄에는 각 줄마다 공백으로 구분된 C개의 수로 보도블록의 초기 상태가 주어진다. 가로 블록은 0, 세로 블록은 1로 표시된다. 그다음 줄에 이동 규칙의 개수 N이 주어지고 ($0 \le N \le 10$), 이어지는 N개의 줄에 규칙 r, c가 주어진다 ($-R \le r \le R$, $-C \le c \le C$). 이는 현재 위치가 $(0, 0)$일 때 $(0+r, 0+c)$로 이동할 수 있다는 뜻이다. 왼쪽 위 블록이 $(0, 0)$이고 오른쪽 아래 블록이 $(R-1, C-1)$이다.

준규가 출근하는 데 필요한 최소 걸음 수를 출력한다. 출근할 수 없으면 -1을 출력한다.