#include <bits/stdc++.h>

#define MAXN 1000006

#define INF 99999999999

long long a[MAXN];
long long b[MAXN];
long long c[MAXN];

using namespace std;

void prepare(int n, int m) {
    int s = m + 2;

    // sa strane upisemo INF
    for(int i = 0; i <= n+1; i++) {
        a[i * s + 0] = INF;
        a[i * s + m + 1] = INF;
        b[i * s + 0] = INF;
        b[i * s + m + 1] = INF;
        c[i * s + 0] = INF;
        c[i * s + m + 1] = INF;
    }
    for(int j = 0; j <= m+1; j++) {
        a[0 * s + j] = INF;
        a[(n + 1) * s + j] = INF;
        b[0 * s + j] = INF;
        b[(n + 1) * s + j] = INF;
        c[0 * s + j] = INF;
        c[(n + 1) * s + j] = INF;
    }

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            if(i == 1 && j == 1)
                b[i * s + j] = a[i * s + j];
            else
                b[i * s + j] = a[i * s + j] + min(b[i * s + j - 1], b[(i - 1) * s + j]);

    for(int i = n; i >= 1; i--)
        for(int j = m; j >= 1; j--)
            if(i == n && j == m)
                c[i * s + j] = a[i * s + j];
            else
                c[i * s + j] = a[i * s + j] + min(c[i * s + j + 1], c[(i + 1) * s + j]);
}

int main()
{
    int n, m;
    cin >> n >> m;

    int s = m + 2;

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin >> a[i * s + j];

    prepare(n,m);

    int q;
    cin >> q;
    for(int i = 0; i < q; i++) {
        int x, y;
        cin >> x >> y;
        long long r = INF;
        if(y > 1)
            for(int i = x + 1; i <= n; i++)
                r = min(b[i * s + y - 1] + c[i * s + y], r);
        if(x > 1) {
            for(int j = y + 1; j <= m; j++)
                r = min(b[(x - 1) * s + j] + c[x * s + j], r);
        }
        cout << r << endl;
    }
    return 0;
}