#include <bits/stdc++.h>
using namespace std;
typedef unsigned neo;
typedef struct {neo r, k;} tacka;

void najs(vector<vector<neo>>& dp, const vector<vector<neo>>& a, int n, int m) {
    for (int i = 0; i < m; i++) dp[i].resize(n);
    dp[0][0] = a[0][0];
    for (int v = 1; v < n; v++) dp[v][0] = dp[v-1][0] + a[v][0];
    for (int k = 1; k < m; k++) dp[0][k] = dp[0][k-1] + a[0][k];
    for (int v = 1; v < n; v++)
        for (int k = 1; k < m; k++)
            dp[v][k] = min(dp[v-1][k] + a[v][k], dp[v][k-1] + a[v][k]); }

void najs2(vector<vector<neo>>& dp, const vector<vector<neo>>& a, int n, int m) {
    for (int i = 0; i < m; i++) dp[i].resize(n);
    dp[n-1][m-1] = a[n-1][m-1];
    for (int v = n-2; v >= 0; v--) dp[v][m-1] = dp[v+1][m-1] + a[v][m-1];
    for (int k = m-2; k >= 0; k--) dp[n-1][k] = dp[n-1][k+1] + a[n-1][k];
    for (int v = n-2; v >= 0; v--)
        for (int k = m - 2; k >= 0; k--)
            dp[v][k] = min(dp[v+1][k] + a[v][k], dp[v][k+1] + a[v][k]);  }

int main() {
    
    int n, m; cin >> n >> m;
    vector<vector<neo>> mm(n);
    vector<vector<neo>> dp1(n); vector<vector<neo>> dp2(n);
    for (int i = 0; i < n; i++) {
        mm[i].resize(n);
        for (int j = 0; j < m; j++)
        cin >> mm[i][j]; }
    najs(dp1, mm, n, m); 
    najs2(dp2, mm, n, m);

    /*   rekonstrukcija naj  puta - ne treba :( 
    vector<tacka>res;
    tacka t;
    int n2=n-1, m2=m-1;
    t.r = n2, t.k = m2;
    res.push_back(t);
    while (n2!=0 && m2!=0){
        if (mm[n2-1][m2] < mm[n2][m2-1]){
            n2--;
            t.r=n2; t.k=m2; res.push_back(t); }
        else {
            m2--;
            t.r=n2; t.k=m2; res.push_back(t); }  }
    while (n2>0){t.r=--n2;t.k=0;res.push_back(t);}
    while (m2>0){t.r=0;t.k=--m2;res.push_back(t);} 

privremeni ispis
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++)
            cout << dp1[i][j] << " ";    }
    cout << endl;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++)
            cout << dp2[i][j] << " ";    } 
    cout << endl;

    for (int i = 0; i < res.size(); i++) 
        cout << res[i].r << "," << res[i].k << " ";  */

    int q; cin >> q; // upiti
    while (q--) {
        int r, k; cin >> r >> k; r--; k--;
        /*da li je deo resenja - nije bitno   :(  
        bool deo = false;
        for (int i = 0; i < res.size(); i++) 
            if (res[i].r == r && res[i].k == k) deo = true;        
        if (deo) cout << "da" << endl; 
        else cout << "ne" << endl; */


        //nadji najbolje resenje pre bloka na r, k
        neo najr, najk, naj = numeric_limits<unsigned int>::max();

        if (r>0) { // horizontala
            for (int i = k+1; i < m; i++){
                if (dp1[r-1][i] + dp2[r][i] < naj) {
                    naj=dp1[r-1][i] + dp2[r][i]; 
                    najr= r-1; 
                    najk= i; } } }

        if (k>0) { // vertikala
            for (int i = r+1; i < n; i++){
                if (dp1[i][k-1] + dp2[i][k]<naj) {
                    naj=dp1[i][k-1] + dp2[i][k];
                    najr= i;
                    najk= k-1; } } }    
        cout << naj << endl; 

        //cout << dp1[najr][najk] + dp2[najr][najk] - mm[najr][najk]<<endl;       


    }

    return 0;     }