#include <bits/stdc++.h>
using namespace std;

#define ios ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define ull unsigned long long
#define inf INT_MAX
#define llinf LLONG_MAX
#define mt make_tuple
#define mp make_pair
#define parll pair<ll,ll>
#define parii pair<int,int>
#define frs first
#define sec second
#define neparno(x) (x&1)
#define parno(x) (!neparno(x))
#define lowbit(x) (x&-x)
#define nzd __gcd
#define nzs(e1,e2) (e1/nzd(e1,e2))*e2
#define all(V) V.begin(),V.end()
#define fill(V,v) fill(all(V),v)
#define l_b(BRL,brl) lower_bound( BRL.begin(), BRL.end(), brl )-BRL.begin()-1
#define u_b(BRU,bru) upper_bound( BRU.begin(), BRU.end(), bru )-BRU.begin()
#define mxn 200004

ll n,m,q,rez;
vector < vector<ll> > A,B,C,D,R,K;

int main()
{
    ios;

    cin >> n >> m;
    A.resize(n+2); B.resize(n+2); C.resize(n+2);
    D.resize(n+2); R.resize(n+2); K.resize(n+2);
    for ( ll i = 0; i <= n+1; i++ )
    {
        A[i].resize(m+2); B[i].resize(m+2); C[i].resize(m+2);
        D[i].resize(m+2); R[i].resize(m+2); K[i].resize(m+2);
    }
    for ( ll i = 1; i <= n; i++ )
    {
        for ( ll j = 1; j <= m; j++ )
        {
            cin >> A[i][j];
        }
    }
    for ( ll i = 0; i <= n+1; i++ )
    {
        for ( ll j = 0; j <= m+1; j++ )
        {
            D[i][j] = 0;
            B[i][j] = C[i][j] = K[i][j] = R[i][j] = llinf-inf;
        }
    }

    B[0][1] = 0;
    for ( ll i = 1; i <= n; i++ )
    {
        for ( ll j = 1; j <= m; j++ )
        {
            B[i][j] = min(B[i-1][j],B[i][j-1])+A[i][j];
        }
    }
    ll i,j;
    rez = B[n][m];

    C[n][m+1] = 0;
    for ( i = n; i >= 1; i-- )
    {
        for ( j = m; j >= 1; j-- )
        {
            C[i][j] = min(C[i+1][j],C[i][j+1])+A[i][j];
        }
    }
    for ( i = 1; i <= n; i++ )
    {
        for ( j = 1; j <= m; j++ )
        {
            D[i][j] = B[i][j]+C[i][j]-A[i][j];
        }
    }

    for ( i = 1; i <= n; i++ )
    {
        for ( j = m; j >= 1; j-- )
        {
            R[i][j] = min( R[i][j+1], D[i][j] );
        }
    }
    for ( j = 1; j <= m; j++ )
    {
        for ( i = n; i >= 1; i-- )
        {
            K[i][j] = min( K[i+1][j], D[i][j] );
        }
    }

    cin >> q;
    ll a,b;
    while ( q-- )
    {
        cin >> a >> b;
        if ( D[a][b] != rez )
        {
            cout << rez << "\n";
            continue;
        }
        ll k=llinf,r=llinf;
        if ( a+1 <= n && b-1 >= 1 )
        {
            k = K[a+1][b-1];
        }
        if ( a-1 >= 1 && b+1 <= m )
        {
            r = R[a-1][b+1];
        }
        cout << min(r,k) << "\n";
    }

    return 0;
}