#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <iomanip> 
#include <map>
#include <string>
#include <list>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <iterator>
#include <queue>
#include <set>


#define f(n) for (long long i = 0; i < n; i++)
#define f0(n) for (int j = 0; j < n; j++)
#define co(n) cout << n << "\n";

using namespace std;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;
    vector<vector<int>> nm(n);
    f(n)
    {
        vector<int> x(m);
        f0(m) cin >> x[j];
        nm[i] = x;
    }
    int q;
    cin >> q;
    vector<pair<int, int>> qq(q);
    f(q)
    {
        cin >> qq[i].first >> qq[i].second;
        qq[i].first--;
        qq[i].second--;
    }

    vector<vector<long long>> dp0(n);
    f(n)
    {
        vector<long long> x(m);
        dp0[i] = x;
    }
    dp0[0][0] = nm[0][0];
    for (int i = 1; i < n; i++) dp0[i][0] = dp0[i - 1][0] + nm[i][0];
    for (int i = 1; i < m; i++) dp0[0][i] = dp0[0][i - 1] + nm[0][i];
    for (int i = 1; i < n; i++) for (int j = 1; j < m; j++) dp0[i][j] = nm[i][j] + min(dp0[i][j - 1], dp0[i - 1][j]);

    vector<vector<long long>> dp1(n);
    f(n)
    {
        vector<long long> x(m);
        dp1[i] = x;
    }
    dp1[n - 1][m - 1] = nm[n - 1][m - 1];
    for (int i = n - 2; i >= 0; i--) dp1[i][m - 1] = dp1[i + 1][m - 1] + nm[i][m - 1];
    for (int i = m - 2; i >= 0; i--) dp1[n - 1][i] = dp1[n - 1][i + 1] + nm[n - 1][i];
    for (int i = n - 2; i >= 0; i--) for (int j = m - 2; j >= 0; j--) dp1[i][j] = nm[i][j] + min(dp1[i][j + 1], dp1[i + 1][j]);

    vector<pair<long long, long long>> dp2(n + m - 1);
    vector<pair<int, int>> dp20(n + m - 1);
    f(n + m - 1) dp2[i] = pair<long long, long long>(LLONG_MAX,LLONG_MAX);
    f(n)
    {
        f0(m)
        {
            long long g = dp0[i][j] + dp1[i][j] - nm[i][j];
            if (g < dp2[i + j].first)
            {
                dp2[i + j].second = dp2[i + j].first;
                dp20[i + j].second = dp20[i + j].first;
                dp2[i + j].first = g;
                dp20[i + j].first = i;
            }
            else if (g < dp2[i + j].second)
            {
                dp2[i + j].second = g;
                dp20[i + j].second = i;
            }
        }
    }

    for(int i0 = 0; i0 < q; i0++)
    {
        int x = qq[i0].first, y = qq[i0].second;
        if (x != dp20[x + y].first) cout << dp2[x + y].first << "\n";
        else cout << dp2[x + y].second << "\n";
    }
}