시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 920 223 173 23.036%

문제

준규는 오랜만에 회사에 출근하려 한다. 준규는 수학을 엄청 좋아해서 항상 규칙을 정하는데, 강남역에서 내린 준규는 회사까지 가는 길에 깔려있는 보도블록을 보고 규칙을 정하기 시작했다.

  1. 세로 블록만 밟는다. (시작은 첫 번째 row의 세로 블록 중 아무 곳에서나 가능하다.)
  2. 특정 규칙(예를 들어 상하좌우, 체스의 나이트 이동 규칙 등)으로 이동한다.
  3. 첫 번째 row에서 출발하여 마지막 row에 도착하면 출근에 성공한 것이다.
  4. 마지막으로 준규는 걷는 것이 매우 귀찮아서 최소한의 걸음으로 출근을 하고 싶다.

위 보도블록 상태를 이용하여 간단한 예시를 들어보자. 1번 규칙으로 밟을 수 있는 블록은 세로 블록이며(색칠 된 블록), 이동 규칙이 오른쪽 이미지와 같다면, 준규는 회사로 가는 여러 경로 중 점선과 실선의 방법으로 출근을 할 수 있다. 실선은 세 걸음으로 출근이 가능한 반면 점선은 두 걸음에 출근이 가능하다.

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

입력

첫 번째 줄에는 보도블록의 세로, 가로 R, C(1 ≤ R, C ≤ 1,000)크기가 주어진다. 다음 R개의 줄에는 C개의 문자로 이루어진 보도블록의 초기 상태가 주어진다. (가로 블록은 0로 표시되고, 세로 블록은 1로 표시된다.) 그 다음 줄에 이동 가능한 규칙의 개수 N(0 ≤ N ≤ 10)이 주어지고 그 다음 N개의 줄에 걸쳐 규칙 r(-R ≤ r ≤ R), c(-C ≤ c ≤ C)가 주어진다. 이 뜻은 현재 위치가 (0, 0) 일 때 (0+r, 0+c)로 이동 할 수 있음을 의미한다. ((0,0)왼쪽 위, (R – 1, C – 1)오른쪽 아래 블록이다.)

출력

준규가 출근을 하는데 최소 몇 번의 걸음을 걸어야 하는지 출력한다. 만약 출근할 수 없다면 -1을 출력한다.

예제 입력 1

4 5
1 0 1 0 1
0 1 1 0 0
1 1 0 1 0
1 0 1 1 1
8
-2 -1
-2 1
-1 -2
-1 2
1 -2
1 2
2 -1
2 1

예제 출력 1

2