//  ? ? ? ? ? ? ?
//  ? @roadfromroi ?
//  ? ? ? ? ? ? ?
#include <iostream>
#include "vector"
#include "algorithm"
#include "numeric"
#include "climits"
#include "iomanip"
#include "bitset"
#include "cmath"
#include "map"
#include "deque"
#include "array"
#include "set"
#define all(x) x.begin(), x.end()
using namespace std;
#define int long long
void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n, vector<int>(m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> a[i][j];
        }
    }
    vector<vector<int>> dp1(n, vector<int>(m, 1e18)), dp2 = dp1, dp = dp1;
    dp1[0][0] = a[0][0];
    dp2.back().back() = a.back().back();
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (i != 0)
                dp1[i][j] = min(dp1[i][j], dp1[i-1][j] + a[i][j]);
            if (j != 0)
                dp1[i][j] = min(dp1[i][j], dp1[i][j-1] + a[i][j]);
        }
    }
    for (int i = n-1; i >= 0; --i) {
        for (int j = m-1; j >= 0; --j) {
            if (i != n-1)
                dp2[i][j] = min(dp2[i][j], dp2[i+1][j] + a[i][j]);
            if (j != m-1)
                dp2[i][j] = min(dp2[i][j], dp2[i][j+1] + a[i][j]);
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            dp[i][j] = dp1[i][j] + dp2[i][j] - a[i][j];
        }
    }
    vector<vector<int>> mnvnz(n, vector<int>(m, 1e18)), mnvrh = mnvnz;
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j + 1 < m; ++j) {
            mnvrh[i][j] = min(mnvrh[i-1][j + 1], dp[i-1][j+1]);
        }
    }
    for (int i = n-2; i >= 0; --i) {
        for (int j = 1; j < m; ++j) {
            mnvnz[i][j] = min(mnvnz[i+1][j - 1], dp[i+1][j-1]);
        }
    }
    int q;
    cin >> q;
    for (int i = 0; i < q; ++i) {
        int a, b;
        cin >> a >> b;
        a--;b--;
        cout << min(mnvnz[a][b], mnvrh[a][b]) << '\n';
    }
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t = 1;
    while (t--) {
        solve();
    }
}