#include <iostream>
#include <bits/stdc++.h> 
/*
3 4
1 2 3 4
5 6 7 8
9 10 11 12
2
1 2
2 4*/
using namespace std;

int A[10000][10000];

void ertekadas(vector<pair<int,int>> vege,int n,int m, int x, int y,priority_queue<pair<int,vector<pair<int,int>>>>& Utvonalak,int jelenlegi)
{
    if(x==n-1&&y==m-1)
    {
        pair<int,vector<pair<int,int>>> B;
        jelenlegi+=A[x][y];
        B.first=-jelenlegi;
        B.second=vege;
        Utvonalak.push(B);
        return;
    }
    pair<int,int> B;
    B.first=x;
    B.second=y;
    vege.push_back(B);
    jelenlegi+=A[x][y];
if(x<n-1)
{
    x++;
    ertekadas(vege,n,m,x,y,Utvonalak,jelenlegi);
    x--;
}
if(y<m-1)
{
    y++;
    ertekadas(vege,n,m,x,y,Utvonalak,jelenlegi);
}
}

int main()
{
int a,b,q;
vector<int> megoldas;
vector<pair<int,int>> vege;
cin>>a>>b;
priority_queue<pair<int,vector<pair<int,int>>>> Utvonalak;
priority_queue<pair<int,vector<pair<int,int>>>> MentesUtvonalak;
pair<int,vector<pair<int,int>>> B;
for(int i=0;i<a;i++)
{
    for(int j=0;j<b;j++)
    {
        int c;
        cin>>c;
        A[i][j]=c;
    }
}
ertekadas(vege,a,b,0,0,Utvonalak,0);
MentesUtvonalak=Utvonalak;
cin>>q;
for(int i=0;i<q;i++)
{
    int c,d;
    bool mehet=true;
    cin>>c>>d;
    c--;
    d--;
    Utvonalak=MentesUtvonalak;
    while(mehet)
    {
        B=Utvonalak.top();
        if(B.second[c+d].first==c&&B.second[c+d].second==d)
        {
                Utvonalak.pop();
        }
        else
        {
            megoldas.push_back(-B.first);
            mehet=false;
        }
        /*        bool vanebenne=false;
        for(int k=0;k<B.second.size();k++)
        {
            if(B.second[k].first==c&&B.second[k].second==d)
            {
                Utvonalak.pop();
                vanebenne=true;
                break;
            }
        }
        if(!vanebenne)
        {
            megoldas.push_back(-B.first);
            mehet=false;
        }*/
    }
}
for(int i=0;i<q;i++)
{
    cout<<megoldas[i]<<endl;
}
}