스네이크 게임

숏켁은 명랑하제(KAIST 게임개발 동아리 하제에서 매년 진행하는 신입생 게임 개발 행사)에 참가해 자동화된 스네이크 게임을 만들었다. 이 게임의 목표는 스네이크를 길게 만들어 점수를 높이는 것이다. 맵은 $H$행 $W$열의 직사각형 타일로 이루어져 있다.

1. 모든 타일에는 위, 오른쪽, 아래, 왼쪽 화살표 중 하나가 적혀 있다.
2. 일부 타일에는 사과가 올라가 있다.

맵에는 스네이크가 한 마리 있다. 스네이크는 머리, 몸통, 꼬리로 구성된다. 스네이크가 차지한 타일 중 가장 마지막에 차지한 타일이 머리이고, 가장 처음 차지한 타일이 꼬리이다. 나머지 타일은 몸통이다. 처음에 스네이크는 인접한 타일 2개를 차지하며, 그중 하나는 머리, 하나는 꼬리이다. 게임을 시작할 때 점수는 스네이크가 차지한 타일 수이며, 스네이크는 다음 순서로 행동을 반복한다.

1. 머리가 자라날 위치를 정한다. 새 머리 위치는 현재 머리 타일에 적힌 화살표 방향으로 1칸 인접한 칸이다.
   • 단, 타일에 적힌 화살표가 스네이크가 원래 움직이던 방향의 정반대라면 화살표를 무시하고, 원래 움직이던 방향으로 1칸 인접한 칸을 새 머리 위치로 정한다.
   • 처음 상태에서 스네이크가 움직이던 방향은 꼬리에서 머리 방향이다.
2. 새 머리 위치에 사과가 없거나 그 위치가 맵 바깥이면, 꼬리 타일에서 스네이크가 빠져나와 더 이상 그 타일을 차지하지 않는다. 나머지 타일 중 가장 처음 차지한 타일이 새로운 꼬리가 된다.
3. 새 머리 위치에 사과가 있다면 스네이크가 사과를 먹는다. 먹은 사과는 사라진다.
4. 스네이크가 새 머리 위치를 차지한다. 이 위치가 맵 바깥이거나 이미 스네이크가 차지한 타일이면 게임을 즉시 종료한다.
5. 게임 점수를 스네이크가 차지한 타일의 총 개수로 바꾼다.

숏켁은 이 게임에서 나올 수 있는 최대 점수를 알고 싶어 한다. 아트를 그리느라 바쁜 숏켁을 대신해 이 값을 구해주자.

첫 번째 줄에 $H$, $W$, $r_1$, $c_1$, $r_2$, $c_2$가 공백으로 구분되어 주어진다. 맵의 세로 길이는 $H$, 가로 길이는 $W$이고, 뱀의 시작 머리 위치는 $(r_1, c_1)$, 시작 꼬리 위치는 $(r_2, c_2)$이다. 맵의 왼쪽 위 타일 좌표는 $(1, 1)$이고, $r$행 $c$열 타일의 좌표는 $(r, c)$이다. ($3 \le H, W \le 500$; $1 \le r_1, r_2 \le H$; $1 \le c_1, c_2 \le W$; $|r_1-r_2| + |c_1-c_2| = 1$)

다음 $H$개의 줄에는 공백으로 구분된 $W$개의 $0$ 이상 $3$ 이하의 정수가 주어진다. $r$번째 줄의 $c$번째 수는 $(r, c)$ 타일에 적힌 화살표이며, 위, 오른쪽, 아래, 왼쪽 화살표는 각각 $0, 1, 2, 3$으로 주어진다.

다음 줄에는 사과의 개수 $A$가 주어진다. ($1 \le A \le H \times W - 2$)

다음 $A$개의 줄의 $i$번째 줄에는 $i$번째 사과의 위치 $(p_i, q_i)$가 공백으로 구분되어 주어진다. 한 타일에 사과가 두 개 이상 있거나, 처음 스네이크가 있는 타일에 사과가 있는 경우는 주어지지 않는다. ($1 \le p_i \le H$; $1 \le q_i \le W$)

게임에서 나올 수 있는 최대 점수를 출력한다.

맵에 따라서는 게임이 끝나지 않을 수 있으니 주의하라.