Snake Game

Sookkek took part in Myeongrang Hajae, the annual freshman game development event run by the KAIST game development club Hajae, and built an automated snake game. The goal is to make the snake as long as possible to raise the score. The map is a grid of $H$ rows and $W$ columns of rectangular tiles.

1. Every tile has one of an up, right, down, or left arrow.
2. Some tiles have an apple on them.

One snake is on the map. It consists of a head, a body, and a tail. Among the tiles the snake occupies, the one it occupied last is the head, and the one it occupied first is the tail. The rest are body tiles. At the start, the snake occupies two adjacent tiles, one head and one tail. The starting score is the number of tiles the snake occupies. The snake repeats the following steps.

1. Choose the tile where the head grows. The new head is the cell one step from the current head in the direction of the arrow on the head's tile.
   • However, if the arrow on the tile points opposite to the snake's moving direction, ignore the arrow and take the cell one step in the moving direction instead.
   • At the start, the snake's moving direction is from the tail toward the head.
2. If there is no apple at the new head position, or the position is outside the map, the snake leaves the tail tile and no longer occupies it. The first tile the snake occupied among the remaining tiles becomes the new tail.
3. If there is an apple at the new head position, the snake eats it. An eaten apple disappears.
4. The snake occupies the new head position. If this position is outside the map or already occupied by the snake, the game ends immediately.
5. The score becomes the total number of tiles the snake occupies.

Sookkek wants to know the maximum score this game can reach. Find it for him while he is busy drawing art.

The first line contains $H$, $W$, $r_1$, $c_1$, $r_2$, and $c_2$, separated by spaces. The map has $H$ rows and $W$ columns. The snake's starting head is at $(r_1, c_1)$, and its starting tail is at $(r_2, c_2)$. The top-left tile is $(1, 1)$, and the tile in row $r$ and column $c$ is $(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$)

The next $H$ lines each contain $W$ integers from $0$ to $3$, separated by spaces. The $c$-th number on the $r$-th line is the arrow on tile $(r, c)$. Up, right, down, and left arrows are $0, 1, 2, 3$.

The next line contains the number of apples $A$. ($1 \le A \le H \times W - 2$)

The next $A$ lines each contain two integers $p_i$ and $q_i$, separated by a space. The $i$-th apple is at $(p_i, q_i)$. No tile has two or more apples, and no apple is on the tile where the snake starts. ($1 \le p_i \le H$; $1 \le q_i \le W$)

Print the maximum score this game can reach.

The game may never end depending on the map.