#include "bits/stdc++.h"
#define ll long long
#define pb push_back
using namespace std;


void solve() {
    ll n,m,q,x,y;
    cin>>n>>m;
    vector<vector<ll> > a(n,vector<ll>(m));
    vector<vector<ll> > poc(n,vector<ll>(m));
    vector<vector<ll> > kraj(n,vector<ll>(m));
    vector<vector<ll> > kor(n,vector<ll>(m));
    vector<vector<ll> > red(n,vector<ll>(m));
    vector<vector<ll> > kolona(n,vector<ll>(m));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>a[i][j];
        }
    }
    poc[0][0]=a[0][0];
    for(int i=1;i<n;i++){
        poc[i][0]=poc[i-1][0]+a[i][0];
    }
    for(int j=1;j<m;j++){
        poc[0][j]=poc[0][j-1]+a[0][j];
    }
    for(int i=1;i<n;i++){
        for(int j=1;j<m;j++){
            poc[i][j]=min(poc[i-1][j],poc[i][j-1])+a[i][j];
        }
    }
    
        kraj[n-1][m-1]=a[n-1][m-1];
    for(int i=n-2;i>=0;i--){
        kraj[i][m-1]=kraj[i+1][m-1]+a[i][m-1];
    }
    for(int j=m-2;j>=0;j--){
        kraj[n-1][j]=kraj[n-1][j+1]+a[n-1][j];
    }
    for(int i=n-2;i>=0;i--){
        for(int j=m-2;j>=0;j--){
            kraj[i][j]=min(kraj[i+1][j],kraj[i][j+1])+a[i][j];
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            kor[i][j]=poc[i][j]+kraj[i][j]-a[i][j];
        }
    }
    for(int i=0;i<n;i++){
        red[i][0]=kor[i][0];
        for(int j=1;j<m;j++){
            red[i][j]=min(red[i][j-1],kor[i][j]);
        }
    }
    for(int j=0;j<m;j++){
        kolona[0][j]=kor[0][j];
        for(int i=1;i<n;i++){
            kolona[i][j]=min(kolona[i-1][j],kor[i][j]);
        }
    }
    cin>>q;
    for(int k=0;k<q;k++){
        cin>>x>>y;
        x--;
        y--;
        if(x==n-1||y==0){
            cout<<kolona[x-1][y+1]<<endl;
        }
        else if(x==0||y==m-1){
            cout<<red[x+1][y-1]<<endl;
        }
        else{
            cout<<min(kolona[x-1][y+1],red[x+1][y-1])<<endl;
        }
    }
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int t=1;
    /*
    cin>>t;
    //*/
    while(t--) {
        solve();
    }
}