#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;
int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    long long a[n][m];
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) cin >> a[i][j];
    long long b[n][m];
    b[0][0] = a[0][0];
    for (int i = 1; i < n; i++) b[i][0] = b[i - 1][0] + a[i][0];
    for (int i = 1; i < m; i++) b[0][i] = b[0][i - 1] + a[0][i];
    for (int i = 1; i < n; i++) for (int j = 1; j < m; j++) b[i][j] = min(b[i - 1][j], b[i][j - 1]) + a[i][j];
    int q;
    cin >> q;
    while(q--) {
        int x, y;
        cin >> x >> y;
        x--, y--;
        int p = n - x, q = m - y;
        long long c[p + 1][q + 1];
        c[0][0] = c[1][0] = c[0][1] = c[1][1] = LLONG_MAX;
        if (x != 0) for (int i = 2; i <= q; i++) c[0][i] = b[x - 1][i + y - 1];
        else for (int i = 2; i <= q; i++) c[0][i] = LLONG_MAX;
        if (y != 0) for (int i = 2; i <= p; i++) c[i][0] = b[i + x - 1][y - 1];
        else for (int i = 2; i <= p; i++) c[0][i] = LLONG_MAX;
        for (int i = 1; i <= p; i++) {
            for (int j = 1; j <= q; j++) {
                if (c[i - 1][j] == LLONG_MAX and c[i][j - 1] == LLONG_MAX) c[i][j] = LLONG_MAX;
                else c[i][j] = min(c[i - 1][j], c[i][j - 1]) + a[i + x - 1][j + y - 1];
            }
        }
        cout << c[p][q] << '\n';
    }
    return 0;
}