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

typedef long long ll;
int n, m;
const ll INF = 2000000000;
ll f(int x, int y, vector<vector<ll>>& mapa, vector<vector<ll>>& ans) {
	if (x > m || y > n) return INF;
	//if (x == bx && y == by) return INF;
	if (x == m && y == n) return mapa[n][m];
	if (ans[y][x] != 0) return ans[y][x];

	ll c;

	ll a = f(x + 1, y, mapa, ans);
	ll b = f(x, y + 1, mapa, ans);

	c = min(a, b);
	c += mapa[y][x];
	ans[y][x] = c;
	return c;
}

ll f2(int x, int y, int bx, int by, const vector<vector<ll>>& mapa, vector<vector<ll>>& ans2, const vector<vector<ll>>& ans) {
	if (x > m || y > n) return INF;
	if (x == bx && y == by) return INF;
	if (!(x <= bx && y <= by)) return ans[y][x];
	if (ans2[y][x] != 0) return ans2[y][x];

	ll c;

	ll a = f2(x + 1, y, bx, by, mapa, ans2, ans);
	ll b = f2(x, y + 1, bx, by, mapa, ans2, ans);

	c = min(a, b);
	c += mapa[y][x];
	ans2[y][x] = c;
	return c;
}

void findPath(int x, int y, const vector<vector<ll>>& ans, vector<vector<bool>>& prev){
	if(x == m && y == n) return;

	if (ans[y][x + 1] < ans[y + 1][x]) {
		prev[y][x + 1] = true;
		findPath(x+1, y, ans, prev);
	}
	else {
		prev[y+1][x] = true;
		findPath(x, y+1, ans, prev);
	}
}


int main(int argc, char **argv){
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;
	vector<vector<ll>> mapa(n+2, vector<ll>(m+2, INF));
	vector<vector<ll>> ans(n+2, vector<ll>(m+2, 0));
	vector<vector<bool>> prev(n+2, vector<bool>(m+2, false));

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> mapa[i][j];
		}
	}
	int q;
	cin >> q;
	ll minDist = f(1, 1, mapa, ans);
	//cout << minDist << endl;
	findPath(1,1,mapa,prev);

	vector<vector<ll>> ans2(n+2, vector<ll>(m+2, 0));
	prev[1][1] = true;
	prev[n][m] = true;
	/*
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (prev[i][j]) cout << "#";
			else cout << " ";
		}
		cout << endl;
	}*/
	for (int i = 0; i < q; i++){
		int bx, by;
		cin >> by >> bx;
		if (!prev[by][bx]) {
			cout << minDist << endl;
			continue;
		}

		for (int i = 1; i <= by; i++) { //bx
			for (int j = 1; j <= bx; j++) { //by
				ans2[i][j] = 0;
			}
		}
		cout << f2(1, 1, bx, by, mapa, ans2, ans) << endl;
	}
	return 0;
}