#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, vector<vector<pair<ll, ll>>>& prev) {
	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, prev);
	ll b = f(x, y + 1, mapa, ans, prev);

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

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

	ll c;

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

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

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

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

	}
	else {
		prev[y+1][x] = {x, y};
		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<pair<ll, ll>>> prev(n+2, vector<pair<ll, ll>>(m+2, {-1, -1}));

	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, prev);
	//cout << minDist << endl;
	findPath(1,1,mapa,prev);

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			//cout << prev[i][j].first << " " << prev[i][j].second << "  "; 
		}
		//cout << endl;
	}
	for (int i = 0; i < q; i++){
		int bx, by;
		cin >> by >> bx;
		pair<ll, ll> pp = {-1, -1};
		if (prev[by][bx] == pp) {
			cout << minDist << endl;
		}
		else {
			if (prev[by][bx].second == by) {
				if (by != n) {
					//cout << bx << " " << by << endl;
					//cout << prev[by][bx].first << " " << prev[by][bx].second + 1 << endl;
					cout << minDist + ans[prev[by][bx].second + 1][prev[by][bx].first] - ans[by][bx] << endl;
				}
				else {
					pp = prev[by][bx];
					while (pp.second == n) {
						pp = prev[pp.second][pp.first];
				    }
					cout << minDist + f2(pp.first, pp.second, bx, by, mapa) - ans[pp.second][pp.first] << endl;
				}
			}
			if (prev[by][bx].first == bx) {
				if (bx != m) {
					//cout << bx << " " << by << endl;
					//cout << prev[by][bx].first + 1<< " " << prev[by][bx].second << endl;
					cout << minDist << " " << ans[prev[by][bx].second][prev[by][bx].first + 1] << " " << ans[by][bx] << endl;
				}
				else {
					pp = prev[by][bx];
					while (pp.first == m) {
						pp = prev[pp.second][pp.first];
					}
					cout << minDist + f2(pp.first, pp.second, bx, by, mapa) - ans[pp.second][pp.first] << endl;
				}
			}
		}
		//cout << f(1, 1, bx, by, mapa, ans) << endl;
	}
	return 0;
}