#include <bits/stdc++.h>
using namespace std;
long long n, m, q;
int main(){
	scanf("%lld %lld", &n, &m);
	long long mat[n + 1][m + 1];
	long long dp[n + 1][m + 1];
	long long dp2[n + 1][m + 1];
	long long dpreslevo[n + 1][m + 1];
	long long dpresdesno[n + 1][m + 1];
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			scanf("%lld", &mat[i][j]);
		}
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			if(i == 1 && j == 1)
				dp[i][j] = mat[i][j];
			else if(i > 1 && j == 1)
				dp[i][j] = mat[i][j] + dp[i - 1][j];
			else if(i == 1 && j > 1)
				dp[i][j] = mat[i][j] + dp[i][j - 1];
			else
				dp[i][j] = mat[i][j] + min(dp[i - 1][j], dp[i][j - 1]);
		}
	}
	for(int i = n; i >= 1; i--){
		for(int j = m; j >= 1; j--){
			if(i == n && j == m)
				dp2[i][j] = mat[i][j];
			else if(i < n && j == m)
				dp2[i][j] = mat[i][j] + dp2[i + 1][j];
			else if(i == n && j < m)
				dp2[i][j] = mat[i][j] + dp2[i][j + 1];
			else
				dp2[i][j] = mat[i][j] + min(dp2[i + 1][j], dp2[i][j + 1]);
		}
	}
	dpreslevo[1][2] = mat[1][1] + dp2[2][1];
	for(int i = 2; i < n; i++){
		dpreslevo[i][2] = dp[i][1] + dp2[i + 1][1];
	}
	for(int j = 3; j <= m; j++){
		dpreslevo[n - 1][j] = min(dpreslevo[n - 1][j - 1], dp[n][j - 1] + dp2[n][j - 1] - mat[n][j - 1]);
	}
	for(int i = n - 2; i >= 1; i--){
		for(int j = 3; j <= m; j++){
			dpreslevo[i][j] = min(min(dpreslevo[i + 1][j - 1], min(dpreslevo[i][j - 1], dpreslevo[i + 1][j])), dp[i + 1][j - 1] + dp2[i + 1][j - 1] - mat[i + 1][j - 1]);
		}
	}
	dpresdesno[2][m - 1] = dp[1][m] + dp2[1][m] - mat[1][m];
	for(int j = m - 2; j >= 1; j--){
		dpresdesno[2][j] = min(dpresdesno[2][j + 1], dp[1][j + 1] + dp2[1][j + 1] - mat[1][j + 1]);
	}
	for(int i = 3; i <= n; i++){
		dpresdesno[i][m - 1] = min(dpresdesno[i - 1][m - 1], dp[i - 1][m] + dp2[i - 1][m] - mat[i - 1][m]);
	}
	for(int i = 3; i <= n; i++){
		for(int j = m - 2; j >= 1; j--){
			dpresdesno[i][j] = min(min(dpresdesno[i][j + 1], min(dpresdesno[i - 1][j], dpresdesno[i - 1][j + 1])), dp[i - 1][j + 1] + dp2[i - 1][j + 1] - mat[i - 1][j + 1]);
		}
	}
 	scanf("%lld", &q);
	while(q--){
		long long a, b;
		scanf("%lld %lld", &a, &b);
		if(a == 1 || b == m){
			printf("%lld\n", dpreslevo[a][b]);
		}
		else if(a == n || b == 1)
			printf("%lld\n", dpresdesno[a][b]);
		else
			printf("%lld\n", min(dpresdesno[a][b], dpreslevo[a][b]));
	}
	return 0;
}