#include <bits/stdc++.h>

#define ll long long
#define ld long double
#define pb push_back
#define fi first
#define se second
#define en '\n'
#define sp ' '
#define tb '\t'
#define ri(n) int n; cin >> n
#define rl(n) ll n; cin >> n
#define rs(s) string s; cin >> s
#define rc(c) char c; cin >> c
#define rv(v) for (auto &x : v) cin >> x
#define pven(v) for (auto x : v) cout << x << en
#define pv(v) for (auto x : v) cout << x << sp; cout << en
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define yes cout << "YES" << en
#define no cout << "NO" << en
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
#define ssort(a, b) if (a < b) swap(a, b)
#define bitcnt(a) (__builtin_popcountll(a))
#define bithigh(a) (63-__builtin_clzll(a))
#define lg bithigh
#define highpow(a) (1LL << (ll)lg(a))

using namespace std;

const ll LINF = 4e18;
const int mxN = 1e6+10, INF = 2e9;
ll n, m;
vector<vector<ll> > a, dp[2], mn[2];

void Solve(){

    cin >> n >> m;
    a.assign(n, vector<ll>(m));
    dp[0].assign(n, vector<ll>(m));
    dp[1].assign(n, vector<ll>(m));
    mn[0].assign(n, vector<ll>(m));
    mn[1].assign(n, vector<ll>(m));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> a[i][j];
    dp[0][0][0] = a[0][0];
    for (int i = 1; i < n; i++)
        dp[0][i][0] = a[i][0] + dp[0][i-1][0];
    for (int j = 1; j < m; j++)
        dp[0][0][j] = a[0][j] + dp[0][0][j-1];
    for (int i = 1; i < n; i++)
        for (int j = 1; j < m; j++)
            dp[0][i][j] = a[i][j] + min(dp[0][i-1][j], dp[0][i][j-1]);
    dp[1][n-1][m-1] = a[n-1][m-1];
    for (int i = n-2; ~i; i--)
        dp[1][i][m-1] = a[i][m-1] + dp[1][i+1][m-1];
    for (int j = m-2; ~j; j--)
        dp[1][n-1][j] = a[n-1][j] + dp[1][n-1][j+1];
    for (int i = n-2; ~i; i--)
        for (int j = m-2; ~j; j--)
            dp[1][i][j] = a[i][j] + min(dp[1][i+1][j], dp[1][i][j+1]);
    for (int i = n-1; i; i--){
        for (int j = m-1; j; j--){
            mn[0][i][j] = dp[0][i-1][j] + dp[1][i][j];
            if (j<m-1) smin(mn[0][i][j], mn[0][i][j+1]);
            mn[1][i][j] = dp[0][i][j-1] + dp[1][i][j];
            if (i<n-1) smin(mn[1][i][j], mn[1][i+1][j]);
        }
    }
    ri(q);
    while (q--){
        ri(i); ri(j);
        i--; j--;
        array<ll, 2> ans = {LINF, LINF};
        if (i && j<m-1) ans[0] = mn[0][i][j+1];
        if (j && i<n-1) ans[1] = mn[1][i+1][j];
        cout << min(ans[0], ans[1]) << en;
    }
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0); cerr.tie(0);
    cout << setprecision(12) << fixed;
    cerr << setprecision(12) << fixed;
    cerr << "Started!" << endl;

    int t = 1;
    //cin >> t;
    while (t--)
        Solve();

    return 0;
}