#include <bits/stdc++.h>

using namespace std;

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m;

    cin >> n >> m;

    vector<vector<long long>> mx(n, vector<long long>(m));

    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            cin >> mx[i][j];
        }
    }

    vector<vector<long long>> to(n, vector<long long>(m, LONG_LONG_MAX));
    to[0][0] = 0;

    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            if(!i){
                if(!j) continue;
                to[i][j] = to[i][j-1] + mx[i][j-1];
            }else if(!j) to[i][j] = to[i-1][j] + mx[i-1][j];
            else{
                to[i][j] = to[i][j-1] + mx[i][j-1];
                to[i][j] = min(to[i][j], to[i-1][j] + mx[i-1][j]);
            }
        }
    }

    vector<vector<long long>> from(n, vector<long long>(m, LONG_LONG_MAX));
    from[n-1][m-1] = mx[n-1][m-1];

    for(int i = n-1; i > -1; --i){
        for(int j = m-1; j > -1; --j){
            if(i == n-1){
                if(j == m-1) continue;
                from[i][j] = from[i][j+1] + mx[i][j];
            }else if(j == m-1) from[i][j] = from[i+1][j] + mx[i][j];
            else{
                from[i][j] = from[i][j+1] + mx[i][j];
                from[i][j] = min(from[i][j], from[i+1][j] + mx[i][j]);
            }
        }
    }

    vector<vector<long long>> ttb(n, vector<long long>(m, LONG_LONG_MAX));
    vector<vector<long long>> ltr(n, vector<long long>(m, LONG_LONG_MAX));

    for(int i = 0; i < n; ++i) ltr[i][0] = to[i][0] + from[i][0];
    for(int i = 0; i < m; ++i) ttb[0][i] = to[0][i] + from[0][i];
    
    for(int i = 1; i < n; ++i){
        for(int j = 0; j < m; ++j){
            ttb[i][j] = min(ttb[i-1][j], to[i][j] + from[i][j]);
        }
    }

    for(int i = 1; i < m; ++i){
        for(int j = 0; j < n; ++j){
            ltr[j][i] = min(ltr[j][i-1], to[j][i] + from[j][i]);
        }
    }

    int q;

    cin >> q;

    while(q--){
        int x, y;
        long long ans = LONG_LONG_MAX;

        cin >> x >> y;

        if(y != m && x-2 > -1) ans = ttb[x-2][y];
        if(x != n && y-2 > -1) ans = min(ans, ltr[x][y-2]);
        
        cout << ans << '\n';
    }
    return 0;
}