#include <iostream>
#include <set>
#include <algorithm>
#include <math.h>
#include <queue>
using namespace std;

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

    //ucitavanje matrice navijaca
    int n, m;
    cin>>n>>m;
    int navijaci[n][m];
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) cin>>navijaci[i][j];
    

    //memoizacija matrice navijaca (minimum se gleda as optimal), i pamcenje optimalne vrednosti
    //razlog zbog kog je matrica za memoizaciju par intova je radi lakseg racunanja memoizacije nakon blokade
    //tokom pretrage alternativnog puta (makar je meni lakse)
    pair<int, int> navijaciMem[n][m];
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++)
    {
        if ((i == 0) && (j == 0)) navijaciMem[i][j].first = navijaci[i][j];
        else if (i == 0) navijaciMem[i][j].first = navijaciMem[i][j-1].first + navijaci[i][j];
        else if (j == 0) navijaciMem[i][j].first = navijaciMem[i-1][j].first + navijaci[i][j];
        else navijaciMem[i][j].first = min(navijaciMem[i][j-1].first, navijaciMem[i-1][j].first) + navijaci[i][j];
    }
    int optimalnaVrednost = navijaciMem[n-1][m-1].first;
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) navijaciMem[i][j].second = 0;
    
    //inicijalizacija sortiranih setova za koordinate optimalnog puta, i queuea za koordinate blokada na putu + njihov redosled u ispisu resenja
    set<pair<int, int>> optimalanPut;
    queue<pair<pair<int, int>, int>> vazneBlokade;
    
    //pamcenje optimalnog puta
    int x = n-1, y = m-1;
    pair<int, int> koordinate;
    while(1)
    {
        koordinate.first = x;
        koordinate.second = y;
        if(x<0 || y<0) break;
        optimalanPut.insert(koordinate);
        if(x!=0 && y!=0) (navijaciMem[x-1][y].first < navijaciMem[x][y-1].first) ? x-- : y--;
        else if (x == 0) y--;
        else x--;
    }

    //unos barikada, pritom se cuvaju one koje su na optimalnom putu
    //u slucaju da barikada nije na optimalnom putu, u nizu ispisa se upisuje optimalna vrednost
    int q;                                                                                                          
    cin>>q;
    int ispis[q];
    pair<pair<int, int>, int> blokadeIspisPar;
    for (int i = 0; i < q; i++)
    {
        cin>>x>>y;
        koordinate.first = x-1;
        koordinate.second = y-1;
        blokadeIspisPar.first = koordinate;
        blokadeIspisPar.second = i;
        if(optimalanPut.find(blokadeIspisPar.first) != optimalanPut.end()) vazneBlokade.push(blokadeIspisPar);
        else ispis[i] = optimalnaVrednost;
    }
    
    //trazenje alternativnih puteva za blokade, pritom se barikade van novog alternativnog puta brisu
    pair<pair<int, int>, int> trenutnaBlokada;
    while(!vazneBlokade.empty())
    {
        //prva sledeca vazna blokada
        trenutnaBlokada = vazneBlokade.front();
        vazneBlokade.pop();

        //radimo memoizaciju nad onim poljima na kojima blokada moze uticati na rezultat,
        //to su polja koja su ispod i/ili desno od te blokade
        //na svim ostalim poljima vrednonst memoizacije ostaje ista
        //pamtimo novu memoizaciju na drugu vrednost para
        for (int i = trenutnaBlokada.first.first; i < n; i++) for (int j = trenutnaBlokada.first.second; j < m; j++)
        {
            if ((i == trenutnaBlokada.first.first) && (j == trenutnaBlokada.first.second)) navijaciMem[i][j].second = __INT_MAX__;
            else if (i == 0) navijaciMem[i][j].second = __INT_MAX__;
            else if (j == 0) navijaciMem[i][j].second = __INT_MAX__;
            else if (i == trenutnaBlokada.first.first)
            {
                if(j == trenutnaBlokada.first.second + 1) navijaciMem[i][j].second = navijaciMem[i-1][j].first + navijaci[i][j];
                else navijaciMem[i][j].second = min(navijaciMem[i][j-1].second, navijaciMem[i-1][j].first) + navijaci[i][j]; 
            }
            else if (j == trenutnaBlokada.first.second) 
            {
                if(i == trenutnaBlokada.first.first + 1) navijaciMem[i][j].second = navijaciMem[i][j-1].first + navijaci[i][j];
                else navijaciMem[i][j].second = min(navijaciMem[i-1][j].second, navijaciMem[i][j-1].first) + navijaci[i][j];
            }
            else navijaciMem[i][j].second = min(navijaciMem[i][j-1].second, navijaciMem[i-1][j].second) + navijaci[i][j];
        }

        //vrednost na kraju je vrednost alternativnog puta
        ispis[trenutnaBlokada.second] = navijaciMem[n-1][m-1].second;
        for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) navijaciMem[i][j].second = 0;
    }

    //ispis vrednosti
    for (int i = 0; i < q; i++) cout<<ispis[i]<<'\n';
    return 0;
}