#include <bits/stdc++.h>

using namespace std;
int n,m;
int krd(int i, int j)
{
    int s = (m+1)*i + j;
    return s;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    long long a[m*n+m+n+100];
    for (int i=0; i<=n+1; ++i){
        for (int j=0; j<=m+1; ++j){
            if (i*j>0 && i<=n && j<=m){cin>>a[krd(i,j)];}
            else{a[krd(i,j)]=1000000002;}
        }
    }
    long long pm[m*n+m+n+100];
    pm[krd(1,1)]=a[krd(1,1)];
    for (int i=0; i<=n; ++i){
        for (int j=0; j<=m; ++j){
            if (i*j==0){pm[krd(i,j)]=1000000000000007;}
            else if (i*j>1){
                pm[krd(i,j)]=a[krd(i,j)]+min(pm[krd(i-1,j)], pm[krd(i,j-1)]);
            }
            else if (i==1 && j>1){pm[krd(i,j)]=pm[krd(i,j-1)]+a[krd(i,j)];}
            else if (i>1 && j==1){pm[krd(i,j)]=pm[krd(i-1,j)]+a[krd(i,j)];}
        }
    }
    int w[m+n];
    w[m+n-1]=krd(n,m);
    int b=m+n-1;
    int trr=n;
    int trk=m;
    while (b>=0){
        if (pm[krd(trr-1,trk)]<pm[krd(trr,trk-1)]){
            w[b]=krd(trr-1,trk);
            trr--;
        }
        else{
            w[b]=krd(trr,trk-1);
            trk--;
        }
        b--;
    }
    int q;
    cin>>q;
    for (int z=0; z<q; ++z){
        int lr, lk;
        cin>>lr>>lk;
        int xzxz=krd(lr,lk);
        if ((upper_bound(w, w+m+n, xzxz)-w)-(lower_bound(w, w+m+n, xzxz)-w) != 1){
            cout<<pm[krd(n,m)]<<endl;
        }
        else{
            long long ap[m*n+m+n+100];
            memcpy(ap, a, sizeof(a));
            ap[krd(lr,lk)]=100000000000000007;
            long long pmp[m*n+m+n+100];
            pmp[krd(1,1)]=ap[krd(1,1)];
            for (int i=0; i<=n; ++i){
                for (int j=0; j<=m; ++j){
                    if (i*j==0){pmp[krd(i,j)]=1000000000000007;}
                    else if (i*j>1){
                        pmp[krd(i,j)]=ap[krd(i,j)]+min(pmp[krd(i-1,j)], pmp[krd(i,j-1)]);
                    }
                    else if (i==1 && j>1){pmp[krd(i,j)]=pmp[krd(i,j-1)]+ap[krd(i,j)];}
                    else if (i>1 && j==1){pmp[krd(i,j)]=pmp[krd(i-1,j)]+ap[krd(i,j)];}
                }
            }
            cout<<pmp[krd(n,m)]<<endl;
        }
    }
    return 0;
}