#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define INF 0x3f3f3f3f
#define fi first
#define se second

using namespace std;

typedef pair<int, int> ipair;

int Dijkstra(vector<vector<int>>& dohi, vector<int>& sPath, int n, int m, int ires, int jres)
{
    priority_queue<ipair, vector<ipair>, greater<ipair>> pq;
    vector<ipair> dist(n * m, make_pair(INF, 0));

    pq.push(make_pair(0, 0)); //val, coor
    dist[0] = make_pair(dohi[0][0], 0);

    while (!pq.empty())
    {
        int u = pq.top().second;
        pq.pop();

        int iu = u / m;
        int ju = u - (m * iu);

        if (ju + 1 < m && !(iu == ires && ju + 1 == jres))
        {
            int v = m * iu + ju + 1;
            int weight = dohi[iu][ju + 1];
            if (dist[v].fi > dist[u].fi + weight)
            {
                dist[v].fi = dist[u].fi + weight;
                dist[v].se = u;
                pq.push(make_pair(dist[v].fi, v));
            }
        }
        if (iu + 1 < n && !(iu + 1 == ires && ju == jres))
        {
            int v = m * (iu + 1) + ju;
            int weight = dohi[iu + 1][ju];
            if (dist[v].fi > dist[u].fi + weight)
            {
                dist[v].fi = dist[u].fi + weight;
                dist[v].se = u;
                pq.push(make_pair(dist[v].fi, v));
            }
        }

    }
    int curPos = dist[n * m - 1].se;
    sPath[n + m - 2] = n * m - 1;
    for (int i = n + m - 3; i >= 0; i--)
    {
        sPath[i] = curPos; 
        curPos = dist[curPos].se;
    }
    return dist[n * m - 1].fi;
}

int main()
{
    int n, m;
    cin >> n; cin >> m;
    vector<vector<int>> dohi(n, vector<int>(m));
    vector<int> sPath(n + m - 1);
    vector<int> roundAbout(n * m, -1);

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> dohi[i][j];

    int sPathV = Dijkstra(dohi, sPath, n, m, -1, -1);
    
    int q; cin >> q;
    for (int i = 0; i < q; i++)
    {
        int resi; cin >> resi; resi--;
        int resj; cin >> resj; resj--;
        int resv = m * resi + resj;

        if (binary_search(sPath.begin(), sPath.end(), resv))
        {
            if (roundAbout[resv] == -1)
                roundAbout[resv] = Dijkstra(dohi, sPath, n, m, resi, resj);
            cout << roundAbout[resv] << "\n";
        }
        else
        {
            cout << sPathV << "\n";
        }
    }


    return 0;
}