#include <iostream>
#include <vector>

using namespace std;

vector< vector <long long> > x;
vector< vector <long long> > dp1;
vector< vector <long long> > dp2;
vector< vector <long long> > kolone;
vector< vector <long long> > vrste;

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

	long long n, m, i, j;

	cin >> n >> m;

	x.resize(n + 1);
	dp1.resize(n + 1);
	dp2.resize(n + 1);
	kolone.resize(n + 1);
	vrste.resize(n + 1);

	for (i = 0; i < n + 1; i++) {

		x[i].resize(m + 1);
		dp1[i].resize(m + 1);
		dp2[i].resize(m + 1);
		kolone[i].resize(m + 1);
		vrste[i].resize(m + 1);

	}

	for (i = 1; i <= n; i++) {

		for (j = 1; j <= m; j++) {

			cin >> x[i][j];

		}

	}

	for (i = 0; i <= n; i++) {

		for (j = 0; j <= m; j++) {

			dp1[i][j] = 0;
			dp2[i][j] = 0;
			kolone[i][j] = -1;
			vrste[i][j] = -1;
		}

	}

	for (i = 1; i <= n; i++)
		dp1[i][1] = dp1[i - 1][1] + x[i][1];

	for (j = 1; j <= m; j++)
		dp1[1][j] = dp1[1][j - 1] + x[1][j];

	for (i = 2; i <= n; i++) {

		for (j = 2; j <= m; j++) {

			dp1[i][j] = x[i][j] + min(dp1[i - 1][j], dp1[i][j - 1]);

		}

	}

	dp2[n][m] = x[n][m];

	for (i = n - 1; i >= 1; i--)
		dp2[i][m] = dp2[i + 1][m] + x[i][m];

	for (j = m -1; j >= 1; j--)
		dp2[n][j] = dp2[n][j + 1] + x[n][j];

	for (i = n - 1; i >= 1; i--) {

		for (j = m - 1; j >= 1; j--) {

			dp2[i][j] = x[i][j] + min(dp2[i + 1][j], dp2[i][j + 1]);

		}

	}

	for (j = 1; j < m; j++) {

		long long rn;

		kolone[1][j] = dp1[1][j] + dp2[1][j + 1];

		for (i = 2; i <= n; i++) {

			rn = dp1[i][j] + dp2[i][j + 1];

			kolone[i][j] = min(kolone[i - 1][j], rn);

		}

	}

	for (i = 1; i < n; i++) {

		long long rn;

		vrste[i][1] = dp1[i][1] + dp2[i + 1][1];

		for (j = 2; j <= m; j++) {

			rn = dp1[i][j] + dp2[i + 1][j];

			vrste[i][j] = min(vrste[i][j-1], rn);

		}

	}



	long long Q, q, I, J;

	cin >> Q;

	for (q = 0; q < Q; q++) {

		cin >> I >> J;

		long long u1 = vrste[I][J - 1];
		long long u2 = kolone[I - 1][J];

		if (u1 == -1)
			cout << u2 << '\n';
		else {

			if (u2 == -1)
				cout << u1 << '\n';
			else
				cout << min(u1, u2) << '\n';
		}

	}

	return 0;
 }