#include <bits/stdc++.h>

using namespace std;
vector<vector<long long>> a;
vector<vector<long long>> dpp;
vector<vector<long long>> dpk;
vector<vector<bool>> prolazi;
vector<vector<long long>> rez;
int main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin>>n>>m;
    a.resize(n);
    dpp.resize(n);
    dpk.resize(n);
    prolazi.resize(n);
    rez.resize(n);
    for(int i=0;i<n;i++) a[i].resize(m);
    for(int i=0;i<n;i++) dpp[i].resize(m);
    for(int i=0;i<n;i++) dpk[i].resize(m);
    for(int i=0;i<n;i++) prolazi[i].resize(m);
    for(int i=0;i<n;i++) rez[i].resize(m);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            cin>>a[i][j];
            dpp[i][j]=0;
            dpk[i][j]=0;
            prolazi[i][j]=false;
            rez[i][j]=0;
        }
    }
    //dp od pocetnog do polja
    dpp[0][0]=a[0][0];
    for(int i=1;i<m;i++) dpp[0][i]=dpp[0][i-1] + a[0][i];
    for(int i=1;i<n;i++) dpp[i][0]=dpp[i-1][0] + a[i][0];
    for(int i=1;i<n;i++)
    {
        for(int j=1;j<m;j++)
        {
            dpp[i][j]=min(dpp[i-1][j]+a[i][j],dpp[i][j-1]+a[i][j]);
        }
    }

    //dp od polja do kraja

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


    // naci putanju najbolju kada nista nije blokirano

    prolazi[0][0]=true;
    prolazi[n-1][m-1]=true;
    int e=n-1,r=m-1;
    while(e!=0||r!=0)
    {
        if(e!=0&&r!=0)
        {
            if(dpp[e][r-1]==dpp[e][r]-a[e][r])
            {
                prolazi[e][r-1]=true;
                r--;
            }
            else
            {
                prolazi[e-1][r]=true;
                e--;
            }

        }
        else if(e==0)
        {
            prolazi[e][r-1]=true;
            r--;
        }
        else if(r==0)
        {
            prolazi[e-1][r]=true;
            e--;
        }
    }

    /* ispisivanje najboljeg puta    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(prolazi[i][j]) cout<<1<<" ";
            else cout<<0<<" ";
        }
        cout<<endl;
    }*/



    //odredjivanje kad je blokirana neka bitna

    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(!prolazi[i][j]) rez[i][j]=dpp[n-1][m-1];
            else
            {
                long long najmanje=100000000000000000;
                if(n<=m)
                {
                    for(int f=0;f<n;f++)
                    {
                        if(f<i&&j!=m-1) najmanje=min(najmanje,dpp[f][j+1]+dpk[f][j+1]-a[f][j+1]);
                        else if(f>i&&j!=0) najmanje=min(najmanje,dpp[f][j-1]+dpk[f][j-1]-a[f][j-1]);
                    }
                }
                else
                {
                    for(int q=0;q<m;q++)
                    {
                        if(q<j&&i!=n-1) najmanje=min(najmanje,dpp[i+1][q]+dpk[i+1][q]-a[i+1][q]);
                        else if(q>j&&i!=0) najmanje=min(najmanje,dpp[i-1][q]+dpk[i-1][q]-a[i-1][q]);
                    }
                }
                rez[i][j]=najmanje;
            }
        }

    }



    int q;
    cin>>q;
    for(int i=0;i<q;i++)
    {
        int x,y;
        cin>>x>>y;
        cout<<rez[x-1][y-1]<<endl;
    }
    //cout<<dpp[n-1][m-1];
}