#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int m,n;
    cin>>m>>n;
    vector<vector<int>> a(m,vector<int>(n));
    for(int i=0;i<m;i++)
        for(int j=0;j<n;j++)
            cin>>a[i][j];
    vector<vector<long long>> dpg(m,vector<long long>(n)),dpd(m,vector<long long>(n));
    long long s=0;
    for(int j=0;j<n;j++)
    {
        s+=a[0][j];
        dpg[0][j]=s;
    }
    s=0;
    for(int i=0;i<m;i++)
    {
        s+=a[i][0];
        dpg[i][0]=s;
    }
    s=0;
    for(int i=1;i<m;i++)
        for(int j=1;j<n;j++)
        {
            if(dpg[i-1][j]<dpg[i][j-1])
                dpg[i][j]=dpg[i-1][j]+a[i][j];
            else
                dpg[i][j]=dpg[i][j-1]+a[i][j];
        }
    for(int i=m-1;i>=0;i--)
    {
        s+=a[i][n-1];
        dpd[i][n-1]=s;
    }
    s=0;
    for(int j=n-1;j>=0;j--)
    {
        s+=a[m-1][j];
        dpd[m-1][j]=s;
    }
    s=0;
    for(int i=m-2;i>=0;i--)
        for(int j=n-2;j>=0;j--)
        {
            if(dpd[i+1][j]<dpd[i][j+1])
                dpd[i][j]=dpd[i+1][j]+a[i][j];
            else
                dpd[i][j]=dpd[i][j+1]+a[i][j];
        }
    vector<vector<long long>> sufminred(m,vector<long long>(n)), sufminkol(m,vector<long long>(n));
    long long s1,s2;
    for(int i=1;i<m;i++)
    {
        sufminred[i][n-1]=dpg[i-1][n-1]+dpd[i][n-1];
        for(int j=n-2;j>=0;j--)
        {
            s1=dpg[i-1][j+1]+dpd[i][j+1];
            sufminred[i][j]=min(sufminred[i][j+1],s1);
        }
    }
    for(int j=1;j<n;j++)
    {
        sufminkol[m-1][j]=dpg[m-1][j-1]+dpd[m-1][j];
        for(int i=m-2;i>=0;i--)
        {
            s2=dpg[i+1][j-1]+dpd[i+1][j];
            sufminkol[i][j]=min(sufminkol[i+1][j],s2);
        }
    }
    int q,x,y;
    long long ans;
    cin>>q;
    for(int w=0;w<q;w++)
    {
        cin>>x>>y;
        x--;
        y--;
        if(((x>0)&&(y<n-1))&&((x<m-1)&&(y>0)))
            ans=min(sufminred[x][y],sufminkol[x][y]);
        else
        {
            if((x>0)&&(y<n-1))
                ans=sufminred[x][y];
            else
                ans=sufminkol[x][y];
        }
        cout<<ans<<endl;
    }
}