32353번 - 스네이크 게임

문제

숏켁은 명랑하제 (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;$ $\lvert r_1-r_2 \rvert + \lvert c_1-c_2 \rvert = 1)$

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

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

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

출력

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

제한

힌트

맵에 따라 게임이 끝나지 않을 수 있음에 유의하라.