#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll INF=1e18;
ll N,M,res,u;
vector<vector<ll>> mat,dpp,dps,pref,suf;
int main(){
   ios_base::sync_with_stdio(false);
   cin.tie(0);
   cin>>N>>M;
   mat.resize(N+5);
   dpp.resize(N+5);
   dps.resize(N+5);
   pref.resize(N+5);
   suf.resize(N+5);
   for(int j=0;j<=M+5;j++){
      mat[0].push_back(0);
      mat[N+1].push_back(0);
   }
   for(int i=1;i<=N;i++){
      mat[i].push_back(0);
      for(int j=1;j<=M;j++){
         cin>>u;
         mat[i].push_back(u);
      }
      for(int j=1;j<=5;j++)
         mat[i].push_back(0);
   }
   for(int i=0;i<=N+1;i++){
      dpp[i].resize(M+5,INF);
      dps[i].resize(M+5,INF);
      pref[i].resize(M+5,INF);
      suf[i].resize(M+5,INF);
   }
   dpp[1][0]=dpp[0][1]=0;
   for(int i=1;i<=N;i++)
      for(int j=1;j<=M;j++)
         dpp[i][j]=mat[i][j]+min(dpp[i][j-1],dpp[i-1][j]);
   dps[N][M+1]=dps[N+1][M]=0;
   for(int i=N;i>=1;i--)
      for(int j=M;j>=1;j--)
         dps[i][j]=mat[i][j]+min(dps[i+1][j],dps[i][j+1]);
   for(int i=1;i<=N+1;i++)
      for(int j=1;j<=M;j++)
         pref[i][j]=min(pref[i][j-1],dpp[i-1][j]+dps[i][j]);
   for(int i=1;i<=N+1;i++)
      for(int j=M;j>=1;j--)
         suf[i][j]=min(suf[i][j+1],dpp[i-1][j]+dps[i][j]);
   int Q,a,b;
   cin>>Q;
   while(Q--){
      cin>>a>>b;
      cout<<min(pref[a+1][b-1],suf[a][b+1])<<"\n";
   }
  // cout<<"PRAZNIM MEMORIJU"<<endl;
   return 0;
}