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

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	int n, m; cin >> n >> m;
	vector<vector<ll>> x(n, vector<ll>(m));
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> x[i][j];
	
	vector<vector<ll>> dp_to(n, vector<ll>(m));
	dp_to[0][0] = x[0][0];
	for (int i = 1; i < n; i++)
		dp_to[i][0] = dp_to[i - 1][0] + x[i][0];
	for (int i = 1; i < m; i++)
		dp_to[0][i] = dp_to[0][i - 1] + x[0][i];
	for (int i = 1; i < n; i++)
		for (int j = 1; j < m; j++)
			dp_to[i][j] = x[i][j] + min(dp_to[i][j - 1], dp_to[i - 1][j]);
	
	vector<vector<ll>> dp_from(n, vector<ll>(m));
	dp_from[n - 1][m - 1] = x[n - 1][m - 1];
	for (int i = n - 2; i >= 0; i--)
		dp_from[i][m - 1] = x[i][m - 1] + dp_from[i + 1][m - 1];
	for (int i = m - 2; i >= 0; i--)
		dp_from[n - 1][i] = x[n - 1][i] + dp_from[n - 1][i + 1];
	for (int i = n - 2; i >= 0; i--)
		for (int j = m - 2; j >= 0; j--)
			dp_from[i][j] = x[i][j] + min(dp_from[i + 1][j], dp_from[i][j + 1]);
		
	vector<vector<ll>> sums(n, vector<ll>(m));
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)	
			sums[i][j] = dp_from[i][j] + dp_to[i][j] - x[i][j];
	
	vector<vector<ll>> prefix_cols(n, vector<ll>(m));
	for (int col = 0; col < m; col++)
	{
		prefix_cols[0][col] = sums[0][col];
		for (int row = 1; row < n; row++)
			prefix_cols[row][col] = min(prefix_cols[row - 1][col], sums[row][col]);
	}

	vector<vector<ll>> prefix_rows(n, vector<ll>(m));
	for (int row = 0; row < n; row++)
	{
		prefix_rows[row][0] = sums[row][0];
		for (int col = 1; col < m; col++)
			prefix_rows[row][col] = min(prefix_rows[row][col - 1], sums[row][col]);
	}

	int q; cin >> q;
	for (int t = 0; t < q; t++)
	{
		int row, col; cin >> row >> col;
		row--; col--;
		ll sol = LLONG_MAX;
		if (row < n-1 && col > 0)
			sol = min(sol, prefix_rows[row + 1][col - 1]);
		
		if (col < m-1 && row > 0)
			sol = min(sol, prefix_cols[row - 1][col + 1]);
		
		cout << sol << "\n";
	}	

	return 0;
}