#include <iostream>
#include <climits>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    int N,M,Q;
    cin >> N >> M;
    int matrica[N][M];
    int matrica_gore_dole[N][M]; //najkraci put ako krenes od gore levo ka dole desno
    int matrica_dole_gore[N][M]; //najkraci put ako krenes od dole desno ka gore levo
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            cin >> matrica[i][j];
            if(i==0){
                if(j==0){
                    matrica_gore_dole[0][0] = matrica[0][0];
                }
                else{
                matrica_gore_dole[0][j]=matrica[0][j] + matrica_gore_dole[0][j-1];
                    
                }
            }
            else if(j==0){
                matrica_gore_dole[i][0]=matrica_gore_dole[i-1][0]+matrica[i][0];
            }
            else{
                matrica_gore_dole[i][j] = matrica[i][j] +  min(matrica_gore_dole[i-1][j],matrica_gore_dole[i][j-1]);
            }
            
        }
    }
    for(int j=M-1;j>=0;j--){
        for(int i=N-1;i>=0;i--){
            if(i==N-1){
                if(j==M-1){
                    matrica_dole_gore[i][j]= matrica[i][j];
                }
                else{
                matrica_dole_gore[i][j] = matrica[i][j] + matrica_dole_gore[i][j+1];
                }
            }
            else if(j==M-1){
                matrica_dole_gore[i][j] = matrica_dole_gore[i+1][j]  + matrica[i][j];
            }
            else{
                matrica_dole_gore[i][j] = matrica[i][j] + min(matrica_dole_gore[i+1][j],matrica_dole_gore[i][j+1]);
            }
        }
    }
    cin >> Q;
    int blokX,blokY,mini;
    for(int L=0;L<Q;L++){
        mini=INT_MAX;
        cin >> blokX >> blokY;
        blokX--;blokY--;
        if(blokX!=N-1){
            for(int j=0,i=blokX+1;j<blokY;j++){
                mini = min(mini,matrica_dole_gore[i][j]+matrica_gore_dole[i][j]-matrica[i][j]);
            }
        if(blokX!=0){
            for(int j=blokY+1,i=blokX-1;j<M;j++){
                mini = min(mini,matrica_dole_gore[i][j]+matrica_gore_dole[i][j]-matrica[i][j]);
            }
        }
        
        }
        
        cout << mini << endl;
    }
   // for(int i=0;i<N;i++){
      //  for(int j=0;j<M;j++){
       //     cout << matrica_dole_gore[i][j]<< " ";
            
       // }
       // cout << endl;
    //}
}