#include <bits/stdc++.h>
#define MAXN 1000010

using namespace std;

typedef long long ll;

ll n, m, q, x, y;
ll a[MAXN];
ll minSpreda[MAXN], minOtpozadi[MAXN];
ll minVertikale[MAXN], minHorizontale[MAXN];

ll K(ll i, ll j)
{
    return i * m + j;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(ll i = 0; i < n; i++)
    {
        for(ll j = 0; j < m; j++)
        {
            cin >> a[K(i, j)];
        }
    }

    minSpreda[K(0, 0)] = a[K(0, 0)];
    for(ll j = 1; j < m; j++)
    {
        minSpreda[K(0, j)] = minSpreda[K(0, j - 1)] + a[K(0, j)];
    }
    for(ll i = 1; i < n; i++)
    {
        minSpreda[K(i, 0)] = minSpreda[K(i - 1, 0)] + a[K(i, 0)];
    }
    for(ll i = 1; i < n; i++)
    {
        for(ll j = 1; j < m; j++)
        {
            minSpreda[K(i, j)] = min(minSpreda[K(i - 1, j)], minSpreda[K(i, j - 1)]) + a[K(i, j)];
        }
    }

    minOtpozadi[K(n - 1, m - 1)] = a[K(n - 1, m - 1)];
    for(ll j = m - 2; j >= 0; j--)
    {
        minOtpozadi[K(n - 1, j)] = minOtpozadi[K(n - 1, j + 1)] + a[K(n - 1, j)];
    }
    for(ll i = n - 2; i >= 0; i--)
    {
        minOtpozadi[K(i, m - 1)] = minOtpozadi[K(i + 1, m - 1)] + a[K(i, m - 1)];
    }
    for(ll i = n - 2; i >= 0; i--)
    {
        for(ll j = m - 2; j >= 0; j--)
        {
            minOtpozadi[K(i, j)] = min(minOtpozadi[K(i + 1, j)], minOtpozadi[K(i, j + 1)]) + a[K(i, j)];
        }
    }

    for(int j = 1; j <= m - 1; j++)
    {
        minVertikale[K(n - 1, j)] = minSpreda[K(n - 1, j - 1)] + minOtpozadi[K(n - 1, j)];
        for(int i = n - 2; i >= 1; i--)
        {
            minVertikale[K(i, j)] =  min(minSpreda[K(i, j - 1)] + minOtpozadi[K(i, j)], minVertikale[K(i + 1, j)]);
        }
    }
    for(int i = 1; i <= n - 1; i++)
    {
        minHorizontale[K(i, m - 1)] = minSpreda[K(i - 1, m - 1)] + minOtpozadi[K(i, m - 1)];
        for(int j = m - 2; j >= 1; j--)
        {
            minHorizontale[K(i, j)] = min(minSpreda[K(i - 1, j)] + minOtpozadi[K(i, j)], minHorizontale[K(i, j + 1)]);
        }
    }

    cin >> q;
    while(q--)
    {
        cin >> x >> y;
        x--;
        y--;
        if(x > 0 && y > 0 && x < n - 1 && y < m - 1)
        {
            cout << min(minVertikale[K(x + 1, y)], minHorizontale[K(x, y + 1)]) << "\n";
        }
        else if(x == 0 || y == m - 1)
        {
            cout << minVertikale[K(x + 1, y)] << "\n";
        }
        else
        {
            cout << minHorizontale[K(x, y + 1)] << "\n";
        }
    }
    return 0;
}