#include <bits/stdc++.h>

using namespace std;

	int n, m;
int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	map<int, pair<int,int>> eych;
	cin >> n >> m;
	long long h[n][m], hh[n][m], hhh[n][m];
	
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			cin >> h[i][j];
			hh[i][j] = h[i][j];
			hhh[i][j] = hh[i][j];
		}
	}
	for(int j = 1; j < m; j++) {
		h[0][j] = h[0][j] + h[0][j - 1];
	}
	for(int i = 1; i < n; i++) {
		h[i][0] = h[i][0] + h[i - 1][0];
	}
	for(int i = 1; i < n; i++) {
		for(int j = 1; j < m; j++) {
			h[i][j] = h[i][j] + min(h[i - 1][j], h[i][j - 1]);
		}
	}
	for(int j = 1; j < m; j++) {
		hh[n - 1][m - 1 - j] = hh[n - 1][m - 1 - j] + hh[n - 1][m - 1 - j + 1];
		h[n - 1][m - 1 - j] += hh[n - 1][m - 1 - j] - hhh[n - 1][m - 1 - j];
		eych[n - 1 + m - 1 - j].first = h[n - 1][m - 1 - j];
	//	cout << eych[n - 1 + m - 1 - j].first << " ";
	}
	for(int i = 1; i < n; i++) {
		hh[n - 1 - i][m - 1] = hh[n - 1 - i][m - 1] + hh[n - 1 - i + 1][m - 1];
		h[n - 1 - i][m - 1] += hh[n - 1 - i][m - 1] - hhh[n - 1 - i][m - 1];
		eych[n - 1 + m - 1 - i].second = h[n - 1 - i][m - 1];
	//	cout << h[n - 1 - i][m - 1] << " ";
	//	cout << eych[n - 1 + m - 1 - i].first << " ";
		if(eych[n - 1 + m - 1 - i].second < eych[n - 1 + m - 1 - i].first && eych[n - 1 + m - 1 - i].first != 0) {
			long long u = eych[n - 1 + m - 1 - i].second;
			eych[n - 1 + m - 1 - i].second = eych[n - 1 + m - 1 - i].first;
			eych[n - 1 + m - 1 - i].first = u;
		//	cout << eych[n - 1 + m - 1 - i].second << " " << eych[n - 1 + m - 1 - i].first << "\n";
		}
	}
	for(int i = n - 2; i >= 0; i--) {
		for(int j = m - 2; j >= 0; j--) {
			if(i == 0 && j == 0)continue;
			hh[i][j] = hh[i][j] + min(hh[i + 1][j], hh[i][j + 1]);	
			h[i][j] += hh[i][j] - hhh[i][j];
			if(eych[i + j].first == 0) {
				if(h[i][j] > eych[i + j].second) {
					eych[i + j].first = eych[i + j].second;
					eych[i + j].second = h[i][j];
				}
				else eych[i + j].first = h[i][j];
			}
			else if(eych[i + j].second == 0) {
				if(h[i][j] > eych[i + j].first) {
					eych[i + j].second = h[i][j];
				}
				else {
					eych[i + j].second = eych[i + j].first;
					eych[i + j].first = h[i][j];
				}
			}
			else if(eych[i + j].first > h[i][j]) {
				long long u = eych[i + j].first;
				eych[i + j].first = h[i][j];
				eych[i + j].second = u;
			}
			else if (eych[i + j].second > h[i][j]) {
				eych[i + j].second = h[i][j];
			}
		}
	}
	int q;
	cin >> q;
	for(int i = 0; i < q; i++) {
		int x, y;
		cin >> x >> y;
		if(h[x - 1][y - 1] == eych[x + y - 2].first) cout << eych[x + y - 2].second << "\n";
		else cout << eych[x + y - 2].first << "\n";
	}
	
	return 0;
}