#include <bits/stdc++.h>
#define FAST {ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
#define FILES {freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);}
#define ll long long
#define ull unsigned long long
#define pqueue priority_queue
#define pb push_back
#define fi first
#define se second
#define ld long double
#define pii pair<int,int>
#define pll pair<long long,long long>
#define all(a) (a).begin(), (a).end()
#define mp make_pair 
using namespace std;
// order_of_key -> # less than k
// find_by_order -> k-th element
// pq max element
 
const double eps = 0.00000001;
const int NMAX = 1e6+10;
const ll inf = LLONG_MAX/3;
const ll modi = 998244353;

void solve() {
    ll n,m;
    cin >> n >> m;
    vector<vector<ll>>mat(n,vector<ll>(m));
    vector<vector<ll>>dp1(n,vector<ll>(m,inf));
    vector<vector<ll>>dp2(n,vector<ll>(m,inf));
    vector<vector<ll>>dp(n,vector<ll>(m,inf));
    vector<vector<ll>>nez(n,vector<ll>(m,inf));
    for (int i = 0 ; i < n ; i++ ) {
        for (int j = 0; j < m ; j++ ) {
            cin >> mat[i][j];
        }
    }

    for (int i = n-1; i >= 0 ; i-- ) {
        for (int j = m-1 ; j >= 0 ; j-- ) {
            if ( j < m-1 ) {
                dp2[i][j] = min(dp2[i][j+1], dp2[i][j]);
            }
            if ( i < n-1 ) {
                dp2[i][j] = min(dp2[i+1][j], dp2[i][j]);
            }
            if ( dp2[i][j] == inf ) dp2[i][j] = 0;
            dp2[i][j] += mat[i][j];
        }
    }
    for (int i = 0; i < n ; i++ ) {
        for (int j = 0 ; j < m ; j++ ) {
            if ( j > 0 ) {
                dp1[i][j] = min(dp1[i][j-1], dp1[i][j]);
            }
            if ( i > 0 ) {
                dp1[i][j] = min(dp1[i-1][j], dp1[i][j]);
            }
            if ( dp1[i][j] == inf ) dp1[i][j] = 0;
            dp1[i][j] += mat[i][j];
            dp[i][j] = dp1[i][j] + dp2[i][j] - mat[i][j];
        }
    }
    for (int i = 1; i < n ; i++ ) {
        ll mini = inf;
        for (int j = 0 ; j < m ; j++ ) {
            nez[i-1][j] = min(nez[i-1][j], mini);
            mini = min(mini, dp[i][j]);
        }
    }

    for (int i = 0; i < n-1 ; i++ ) {
        ll mini = inf;
        for (int j = m-1 ; j > 0 ; j-- ) {
            nez[i+1][j] = min(nez[i+1][j], mini);
            mini = min(mini, dp[i][j]);
        }
    }
    
    int q;
    cin >> q;
    while(q--) {
        int a,b;
        cin >> a >> b;
        a--;b--;
        cout << nez[a][b] << endl;
    }
}

int main () { 
    FAST
    


    int t=1;

    /*
    cin >> t;
    //*/

    int i = 1;
    while(t--) {
        //cout << "Case #" << i++ << ": " ;
        solve();
    }
}