#include <bits/stdc++.h>
using namespace std;

typedef tuple<unsigned long long,int,int,int,int> cvor;
typedef tuple<unsigned long long,int,int> cvor2;
typedef pair<int,int> pret;

unsigned long long minPut(int n,int m,int x,int y,const vector<vector<int>>& put,
                          vector<vector<int>>& roditelji){
    vector<vector<bool>> posecen(n,vector<bool>(m));
    vector<vector<pret>> parovi(n,vector<pret>(m));
    priority_queue<cvor,vector<cvor>,greater<cvor>> red;
    red.emplace(put[0][0],0,0,0,0);
    int a,b,p1,p2;
    unsigned long long r;
    while(!red.empty()){
        tie(r,a,b,p1,p2) = red.top();
        red.pop();
        if(a == n-1 && b == m-1){
            parovi[a][b].first = p1;
            parovi[a][b].second = p2;
            int u = n-1,v = m-1;
            while(u != 0 || v != 0){
                roditelji[u][v] = 1;
                int u1 = parovi[u][v].first;
                int v1 = parovi[u][v].second;
                u = u1; v = v1;
            }
            return r;
        }
        if(posecen[a][b]) continue;
        posecen[a][b] = true;
        parovi[a][b].first = p1;
        parovi[a][b].second = p2;
        if((b < m-1) && (a != x || b+1 != y) && !posecen[a][b+1]) red.emplace(r+put[a][b+1],a,b+1,a,b);
        if((a < n-1) && (a+1 != x || b != y) && !posecen[a+1][b])red.emplace(r+put[a+1][b],a+1,b,a,b);
    }
}

unsigned long long minPut2(int n,int m,int x,int y,const vector<vector<int>>& put){
    vector<vector<bool>> posecen(n,vector<bool>(m));
    priority_queue<cvor2,vector<cvor2>,greater<cvor2>> red;
    red.emplace(put[0][0],0,0);
    int a,b;
    unsigned long long r;
    while(!red.empty()){
        tie(r,a,b) = red.top();
        red.pop();
        if(a == n-1 && b == m-1) return r;
        if(posecen[a][b]) continue;
        posecen[a][b] = true;
        if((b < m-1) && (a != x || b+1 != y) && !posecen[a][b+1]) red.emplace(r+put[a][b+1],a,b+1);
        if((a < n-1) && (a+1 != x || b != y) && !posecen[a+1][b])red.emplace(r+put[a+1][b],a+1,b);
    }
}

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

    int n,m;
    cin >> n >> m;
    vector<vector<int>> put(n,vector<int>(m));
    for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++){
            cin >> put[i][j];
        }
    }
    int q;cin >> q;
    vector<vector<int>> roditelji(n,vector<int>(m));
    unsigned long long najkraci = minPut(n,m,-1,-1,put,roditelji);
    while(q--){
        int x,y;
        cin >> x >> y;x--;y--;
        if(roditelji[x][y] == 0) cout << najkraci << "\n";
        else cout << minPut2(n,m,x,y,put) << "\n";
    }
}