#include <iostream>
#define forn(i, n) for (int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
const ll INF = 2e15 + 312432;
int n, m, q;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    ll a[n][m], dp1[n][m], dp2[n][m];
    forn(i, n) forn(j, m) cin >> a[i][j];

    dp1[0][0] = a[0][0];
    dp2[n-1][m-1] = a[n-1][m-1];
    forn(i, n) forn(j, m) if (i != 0 || j != 0) dp1[i][j] = a[i][j] + min((i == 0 ? INF : dp1[i-1][j]), (j == 0 ? INF : dp1[i][j-1]));
    for (int i = n-1; i >= 0; i--) for (int j = m-1; j >= 0; j--) 
    if (i != n-1 || j != m-1) dp2[i][j] = a[i][j] + min((i == n-1 ? INF : dp2[i+1][j]), (j == m-1 ? INF : dp2[i][j+1]));

    bool ispath[n][m];
    forn(i, n) forn(j, m) ispath[i][j] = false;
    {
        int x = n-1, y = m-1;
        while (x != 0 || y != 0) {
            ispath[x][y] = true;
            ll left = (x == 0 ? INF : dp1[x-1][y]);
            ll up = (y == 0 ? INF : dp1[x][y-1]);
            if (left < up) x--;
            else y--;
        }
        ispath[0][0] = true;
    }
    ll calc[n][m];
    forn(i, n) forn(j, m) calc[i][j] = -1;

    cin >> q;
    while (q--) {
        int x, y;
        cin >> x >> y;
        x--, y--;
        if (!ispath[x][y]) cout << dp1[n-1][m-1] << endl;
        else {
            if (calc[x][y] != -1) cout << calc[x][y] << endl;
            else {
                ll minv = INF;
                if (x + 1 < n) for (int i = 0; i < y; i++) minv = min(minv, dp1[x+1][i] + dp2[x+1][i] - a[x+1][i]);
                if (y + 1 < m) for (int i = 0; i < x; i++) minv = min(minv, dp1[i][y+1] + dp2[i][y+1] - a[i][y+1]);
                calc[x][y] = minv;
                cout << minv << endl;
            }
        }
    }
}