#include <iostream>
#include <limits.h>


using namespace std;
int minrastojanje(long rastojanja[], bool sptset[], int n, int m)
{
    long min = LONG_MAX;
    int min_index;
    for (int v = 0; v < n * m; v++)
    {
        if (sptset[v] == false && rastojanja[v] <= min)
        {
            min = rastojanja[v];
            min_index = v;
        }
    }
    return min_index;
}
long dikstra(int broj_navijaca[], int n, int m, int x, int y)
{
    long *rastojanja = new long[n*m];
    bool *sptset = new bool[n*m];
    for (int i = 0; i < n * m; i++)
    {
        rastojanja[i] = LONG_MAX;
        sptset[i] = false;
    }
    rastojanja[0] = broj_navijaca[0];
    for (int count = 0; count < n * m - 1; count++)
    {
        int u = minrastojanje(rastojanja, sptset, n, m);
        sptset[u] = true;
        for (int v = 0; v < m * n; v++)
        {
            if (!sptset[v] && (((v == u + 1) && (u + 1) % m != 0) || ((v == u + m) && u + m < n * m)) && rastojanja[u] != LONG_MAX &&
                (rastojanja[u] + broj_navijaca[v] < rastojanja[v]) && (v != ((x - 1) * m + y - 1)))
            {
                rastojanja[v] = rastojanja[u] + broj_navijaca[v];
            }
        }

    }
    return rastojanja[n * m - 1];
}
int main()
{
    int n, m;
    cin >> n >> m;
    int* broj_navijaca = new int[n*m];
    for (int i = 0; i < n * m; i++)
    {
        cin >> broj_navijaca[i];
    }
    int q, x, y;
    cin >> q;
    for (int i = 0; i < q; i++)
    {
        cin >> x >> y;
        cout << dikstra(broj_navijaca, n, m, x, y);
    }
}