#include <bits/stdc++.h>

#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) (x).begin(),(x).end()
#define inv(n) power((n), mod - 2)
#define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
#define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
#define bff(i,a,b) for (int (i) = (b)-1; (i) >= (a); (i)--)
#define bfff(i,a,b) for (int (i) = (b); (i) >= (a); (i)--)
#define sum_overflow(a,b) __builtin_add_overflow_p ((a), (b), (__typeof__ ((a) + (b))) 0)
#define mul_overflow(a,b) __builtin_mul_overflow_p ((a), (b), (__typeof__ ((a) + (b))) 0)

using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
const int mod = 998244353;
//const int mod = 1000000007;







//Note to self: Check for overflow

int main()
{
    FAST;

    int n,m; cin>>n>>m;
    vector<vector<li>> a,dp11,dpnm,dl,gd; //dole levo, gore desno, prefix/suffix max
    ff(i,0,n)
    {
        vector<li> temp(m);
        ff(j,0,m) cin>>temp[j];
        a.push_back(temp);
        dp11.pb(temp);
        dpnm.pb(temp);
        dl.pb(temp);
        gd.pb(temp);
    }

    dp11[0][0]=a[0][0];
    ff(i,1,n) dp11[i][0]=dp11[i-1][0]+a[i][0];
    ff(j,1,m) dp11[0][j]=dp11[0][j-1]+a[0][j];
    ff(i,1,n) ff(j,1,m) dp11[i][j]=min(dp11[i-1][j],dp11[i][j-1])+a[i][j];

    dpnm[n-1][m-1]=a[n-1][m-1];
    bff(i,0,n-1) dpnm[i][m-1]=dpnm[i+1][m-1]+a[i][m-1];
    bff(j,0,m-1) dpnm[n-1][j]=dpnm[n-1][j+1]+a[n-1][j];
    bff(i,0,n-1) bff(j,0,m-1) dpnm[i][j]=min(dpnm[i+1][j],dpnm[i][j+1])+a[i][j];

    /*ff(i,0,n)
    {
        ff(j,0,m) cout<<dp11[i][j]<<" ";
        cout<<endl;
    } cout<<endl;

    ff(i,0,n)
    {
        ff(j,0,m) cout<<dpnm[i][j]<<" ";
        cout<<endl;
    } cout<<endl;*/

    ff(i,0,n) ff(j,0,m)
    {
        gd[i][j]=dp11[i][j]+dpnm[i][j]-a[i][j];
        if (j!=m-1 && i!=0) gd[i][j]=min(gd[i][j],gd[i-1][j+1]);
    }

    bff(i,0,n) bff(j,0,m)
    {
        dl[i][j]=dp11[i][j]+dpnm[i][j]-a[i][j];
        if (i!=n-1 && j!=0) dl[i][j]=min(dl[i][j],dl[i+1][j-1]);
    }

    int q; cin>>q;
    while (q--)
    {
        int x,y; cin>>x>>y; x--,y--;
        if (x==0 || y==m-1) cout<<dl[x+1][y-1]<<"\n";
        else if (x==n-1 || y==0) cout<<gd[x-1][y+1]<<"\n";
        else cout<<min(dl[x+1][y-1],gd[x-1][y+1])<<"\n";
    }
}