#include<bits/stdc++.h>
#define ll long long
#define inf 1e16+8;
using namespace std;
vector<vector<ll>>a;
vector<vector<ll>>dp1;
vector<vector<ll>>dp2;
vector<vector<ll>>res;
vector<vector<ll>>temp;
void resize(int n, int m)
{
    a.resize(n,vector<ll>(m));
    dp1.resize(n,vector<ll>(m));
    dp2.resize(n,vector<ll>(m));
    res.resize(n,vector<ll>(m));
    temp.resize(n,vector<ll>(m));
}
void dodp(int n, int m)
{
    //dp1
    dp1[0][0]=a[0][0];
    for(int i=1;i<n;i++) dp1[i][0]=dp1[i-1][0]+a[i][0];
    for(int i=1;i<m;i++) dp1[0][i]=dp1[0][i-1]+a[0][i];
    for(int i=1;i<n;i++)
        for(int j=1;j<m;j++)
            dp1[i][j]=a[i][j]+min(dp1[i-1][j],dp1[i][j-1]);
    //dp2
    dp2[n-1][m-1]=a[n-1][m-1];
    for(int i=n-2;i>=0;i--) dp2[i][m-1]=dp2[i+1][m-1]+a[i][m-1];
    for(int i=m-2;i>=0;i--) dp2[n-1][i]=dp2[n-1][i+1]+a[n-1][i];
    for(int i=n-2;i>=0;i--)
        for(int j=m-2;j>=0;j--)
            dp2[i][j]=a[i][j]+min(dp2[i+1][j],dp2[i][j+1]);
    return;
}
ll getres(int ip, int jp, int n, int m)
{
    ll sol=LLONG_MAX;
    for(int i=ip+1;i<n;i++)
    {
        if(jp==0)
        {
            temp[i][jp]=inf;
            continue;
        }
        temp[i][jp]=temp[i][jp-1]+a[i][jp];
        if(i!=ip+1) temp[i][jp]=min(temp[i][jp],temp[i-1][jp]+a[i][jp]);
    }
    for(int j=jp+1;j<m;j++)
    {
        if(ip==0)
        {
            temp[ip][j]=inf;
            continue;
        }
        temp[ip][j]=temp[ip-1][j]+a[ip][j];
        if(j!=jp+1) temp[ip][j]=min(temp[ip][j],temp[ip][j-1]+a[ip][j]);
    }
    if(ip==n-1 || jp==m-1) sol=temp[n-1][m-1];
    else
    {
        for(int i=ip+1;i<n;i++) sol=min(sol,temp[i][jp]+dp2[i][jp+1]);
        for(int j=jp+1;j<m;j++) sol=min(sol,temp[ip][j]+dp2[ip+1][j]);
    }
    for(int i=0;i<n;i++) temp[i][jp]=dp1[i][jp];
    for(int j=0;j<m;j++) temp[ip][j]=dp1[ip][j];
    return sol;
}
void pret(int n, int m)
{
    dodp(n,m);
    int i=0,j=0;
    while(i!=n-1 || j!=m-1)
    {
        res[i][j]=-1;
        if(i==n-1) j++;
        else if(j==m-1) i++;
        else if(dp2[i+1][j]<dp2[i][j+1]) i++;
        else j++;
    }
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            temp[i][j]=dp1[i][j];
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(res[i][j]==-1)
            {
                res[i][j]=getres(i,j,n,m)-dp2[0][0];
            }
            else res[i][j]=0;
        }
    }
    return;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n,m;
    cin>>n>>m;
    resize(n,m);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            cin>>a[i][j];
        }
    }
    pret(n,m);

    int q;
    cin>>q;
    while(q--)
    {
        int x,y;
        cin>>x>>y;
        x--;y--;
        cout<<dp2[0][0]+res[x][y]<<endl;
    }

}