#include <bits/stdc++.h>
#define ull unsigned long long
#define pii pair<int, int>
#define N 1000000
using namespace std;
vector<vector<long long>> doha;
vector<vector<long long>> od;
vector<vector<long long>> doo;
vector<vector<long long>> min_od;
vector<vector<long long>> min_doo;

void pisi(vector<vector<long long>> a)
{
    for(int i = 0; i<a.size(); i++){
        for(int j = 0; j<a[i].size(); j++)
            cout<<a[i][j]<<" ";
        cout<<"\n";
    }
    cout<<"\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);

    int n, m;
    cin>>n>>m;
    doha.resize(n);
    od.resize(n);
    doo.resize(n);
    min_od.resize(n);
    min_doo.resize(n);
    for(int i = 0; i<n; i++)
    {
        doha[i].resize(m);
        od[i].resize(m);
        doo[i].resize(m);
        min_od[i].resize(m);
        min_doo[i].resize(m);
        for(int j = 0; j<m; j++)
            cin>>doha[i][j];
    }

    od[0][0]=doha[0][0];
    for(int i = 1; i<n; i++)
        od[i][0]=doha[i][0]+od[i-1][0];
    for(int j = 1; j<m; j++)
        od[0][j]=doha[0][j]+od[0][j-1];

    for(int i = 1; i<n; i++)
        for(int j = 1; j<m; j++)
            od[i][j]=doha[i][j]+min(od[i-1][j], od[i][j-1]);




    doo[n-1][m-1] = doha[n-1][m-1];
    for(int i = n-2; i>=0; i--)
        doo[i][m-1]=doha[i][m-1]+doo[i+1][m-1];
    for(int j = m-2; j>=0; j--)
        doo[n-1][j]=doha[n-1][j]+doo[n-1][j+1];


    for(int i = n-2; i>=0; i--)
        for(int j = m-2; j>=0; j--)
            doo[i][j]=doha[i][j]+min(doo[i+1][j], doo[i][j+1]);

    for(int i = 0; i<n; i++)
        min_od[i][0]=od[i][0]+doo[i][0]-doha[i][0];
    for(int j = 1; j<m; j++)
        for(int i = 0; i<n; i++)
            min_od[i][j]=min(min_od[i][j-1], od[i][j]+doo[i][j]-doha[i][j]);
    //pisi(min_od);



    for(int j = 0; j<m; j++)
        min_doo[0][j]=od[0][j]+doo[0][j]-doha[0][j];

    for(int i = 1; i<n; i++)
        for(int j = m-1; j>-1; j--)
            min_doo[i][j]=min(min_doo[i-1][j], od[i][j]+doo[i][j]-doha[i][j]);
    //pisi(min_doo);





    int q;cin>>q;
    for(int qq = 0; qq<q; qq++)
    {
        int x, y;cin>>x>>y;
        x--;y--;
        long long ans = 1e18;
        if(x<n-1 && y>0)
            ans=min(ans, min_od[x+1][y-1]);
        if(x>0 && y<m-1)
            ans=min(ans, min_doo[x-1][y+1]);
        cout<<ans<<"\n";
    }
    return 0;
}