Commute

Jungyu is going in to the office for the first time in a while. He likes math, so he sets a rule for everything. After getting off at Gangnam Station he looked at the paving blocks laid out on the way to the office and settled on these rules.

1. Step only on vertical blocks. He can start on any vertical block in the first row.
2. Move only by a fixed set of movement rules, for example up, down, left and right, or the moves of a chess knight.
3. Starting from the first row and arriving at the last row counts as a successful commute.
4. Walking is a bother, so he wants the smallest number of steps.

Here is a small example on the paving blocks above. By rule 1 the blocks he can step on are the shaded vertical blocks, and if the movement rules are the ones in the right image, Jungyu can reach the office along the dotted route or the solid route. The solid route takes three steps, while the dotted route takes two.

Jungyu likes math but is not good at it. Write a program that decides whether he can commute under his own rules, and if he can, prints the smallest number of steps he needs.

The first line contains the vertical size R and the horizontal size C of the paving blocks ($1 \le R, C \le 1000$). Each of the next R lines contains C numbers separated by spaces, giving the initial state of the paving blocks. A horizontal block is written as 0 and a vertical block as 1. The next line contains the number of movement rules N ($0 \le N \le 10$), and each of the following N lines contains a rule r, c ($-R \le r \le R$, $-C \le c \le C$). It means that from position $(0, 0)$ he can move to $(0+r, 0+c)$. The top left block is $(0, 0)$ and the bottom right block is $(R-1, C-1)$.

Print the smallest number of steps Jungyu needs to commute. If he cannot commute, print -1.