#include <bits/stdc++.h>
#define int long long
#define MAXIMUM 1000000000000010
using namespace std;

int n,m;
int a[1000010];
int pos[1000010];
int poss[1000010];
int brrzputeva=1;

int resip(int i,int j,int mod1){
    if(i==n-1 && j==m-1) return a[n*m-1];
    int a1=MAXIMUM,a2=MAXIMUM;
    if(i<n-1) a1=resip(i+1,j,0);
    if(j<m-1) a2=resip(i,j+1,0);
    poss[i*m+j]=a[i*m+j]+min(a1,a2);
    if(mod1==1){
        pos[i*m+j]=1;
        if(a1<a2) resip(i+1,j,1);
        else if(a1==a2){
            brrzputeva++;
            resip(i+1,j,2);
            resip(i,j+1,2);
        }else resip(i,j+1,1);
    }else if(mod1==2){
        int mod2=2;
        if(pos[i*m+j]==2){
            brrzputeva--;
            if(brrzputeva==1) mod2=1;
        }
        pos[i*m+j]==mod2;
        if(a1<a2) resip(i+1,j,mod2);
        else if(a1==a2){
            brrzputeva++;
            resip(i+1,j,2);
            resip(i,j+1,2);
        }else resip(i,j+1,mod2);
    }
    return a[i*m+j]+min(a1,a2);
}

bool pr(int i,int j,int i2,int j2){
    if(a[i*m+j]==0 && a[i2*m+j2]!=0) return false;
    return true;
}

int resi(int i,int j,int x,int y){
    if(pos[x*m+y]!=1) return poss[0];
    if(i==n-1 && j==m-1) return a[n*m-1];
    int a1=MAXIMUM,a2=MAXIMUM;
    if(i>x||j>y) return poss[i*m+j];
    if((i+1!=x||j!=y) && i<n-1 && pr(i+1,j,i,j)) a1=resi(i+1,j,x,y);
    if((i!=x||j+1!=y) && j<m-1 && pr(i,j+1,i,j)) a2=resi(i,j+1,x,y);
    return a[i*m+j]+min(a1,a2);
}

signed main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++) cin>>a[i*m+j];
    int q; cin>>q;
    int pom=q;
    int res[500010];
    resip(0,0,1);
    /*for(int i=0;i<n;i++){
        for(int j=0;j<m;j++) cerr<<poss[i*m+j]<<" ";
        cerr<<"\n";
    }
    cerr<<"\n";
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++) cerr<<pos[i*m+j]<<" ";
        cerr<<"\n";
    }*/
    while(q>0){
        int x,y; cin>>x>>y;
        x--; y--;
        /*if((x+1)*(y+1)<(n-x)*(m-y))*/ res[q]=resi(0,0,x,y);
        //else res[q]=resi(n-1,m-1,x,y);
        q--;
    }
    q=pom;
    for(int i=q;i>0;i--) cout<<res[i]<<"\n";
    return 0;
}