Untitled

//
// Created by jin ho Jeon on 2023/11/27.
//

#include <iostream>
#include <queue>
#include <utility>
#include <cstring>


using namespace std;

int n,m;
int MAP[1001][1001];

vector<pair<int,int> > orders;
bool vis[1001][1001];

struct node{
    int y;
    int x;
    int dist;
};

deque<node> que;


void solve(){
    memset(vis, false, sizeof(vis));

    for(int i = 0;i<que.size();i++){
        int y = que[i].y;
        int x = que[i].x;
        vis[y][x] = true;
    }

    // n-1 => break
    int order_length = orders.size();

    while(!que.empty()){

        size_t length = que.size();

        for(size_t i = 0;i<length;i++){
            node cur = que.front();
            int y = cur.y;
            int x = cur.x;
            int dist = cur.dist;
            que.pop_front();
            if(y==n-1){
                cout << dist << '\n';
                return;
            }

            for(int j = 0; j<order_length;j++){
                // inside
                int ny = y + orders[j].first;
                int nx = x + orders[j].second;
                if(0>ny || 0>nx || ny >= n || nx >= m) continue; // inside

                if(MAP[ny][nx]==0 || vis[ny][nx]) continue; // visit and MAP check

                vis[ny][nx] = true;
                node nxt = {ny, nx, dist + 1 };
                que.push_back(nxt);

            }
        }
    }
    cout << -1 << '\n';
    return;
}

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for(int i = 0;i<n;i++){
        for(int j =0;j<m;j++){
            cin >> MAP[i][j];
            if(i==0 && MAP[i][j]==1){
                node tmp = {i, j, 0};
                que.push_back(tmp);

            }
        }
    }

    int o;
    cin >> o;

    int s,e;

    for(int i = 0;i<o;i++){
        cin >> s >> e;
        pair<int, int> tmp = make_pair(s, e);
        orders.push_back(tmp);

    }
    solve();
    return 0;

}