#include <iostream>
#include <vector>
#include <cmath>
#include <unordered_map>
#include <fstream>
#include <string>
#include <queue>

int min(int a, int b) {
	return (a < b) ? a : b;
}


int eval(int x, int y, std::vector<std::vector<int>> a, int n, int k) {
	std::queue<std::pair<int, int>> queue;
	std::vector<std::vector<int>> s(n, std::vector<int>(k, 0));
	s[0][0] = a[0][0];
	queue.push({ 0, 0 });

	while (!queue.empty()) {
		int y1 = queue.front().first;
		int x1 = queue.front().second;
		queue.pop();
		if (y1 == y && x1 == x) {
			continue;
		}
		if (y1 < a.size() - 1) {
			if (s[y1 + 1][x1] != 0) {
				s[y1 + 1][x1] = min(s[y1 + 1][x1], s[y1][x1] + a[y1 + 1][x1]);
			}
			else {
				s[y1 + 1][x1] = s[y1][x1] + a[y1 + 1][x1];
				queue.push({ y1 + 1, x1 });
			}
		}
		if (x1 < a[0].size() - 1) {
			if (s[y1][x1 + 1] != 0) {
				s[y1][x1 + 1] = min(s[y1][x1 + 1], s[y1][x1] + a[y1][x1 + 1]);
			}
			else {
				s[y1][x1 + 1] = s[y1][x1] + a[y1][x1 + 1];
				queue.push({ y1, x1 + 1 });
			}
		}
	}
	return s[n - 1][k - 1];
}


int main()
{
	std::ifstream in("b.txt");
	std::streambuf* cinbuf = std::cin.rdbuf(); //save old buf
	std::cin.rdbuf(in.rdbuf()); //redirect std::cin to in.txt!
	std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0);
	int n, k;
	std::cin >> n >> k;

	std::vector<std::vector<int>> a(n, std::vector<int>(k));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < k; j++) {
			std::cin >> a[i][j];
		}
	}

	std::unordered_map<int, std::unordered_map<int, int>> mem;
	std::unordered_map<int, std::unordered_map<int, int>> res;
	std::vector<std::vector<int>> optimal;
	int op = 0;
	std::vector<std::pair<int, int>> oppath;

	{
		std::queue<std::pair<int, int>> queue;
		std::vector<std::vector<std::vector<std::pair<int, int>>>> paths(n, std::vector<std::vector<std::pair<int, int>>>(k, { {} }));
		std::vector<std::vector<int>> s(n, std::vector<int>(k, 0));
		s[0][0] = a[0][0];
		paths[0][0] = { };
		queue.push({ 0, 0 });

		while (!queue.empty()) {
			int y1 = queue.front().first;
			int x1 = queue.front().second;
			queue.pop();
			if (y1 < a.size() - 1) {
				if (s[y1 + 1][x1] != 0) {
					int a1 = s[y1 + 1][x1];
					int a2 = s[y1][x1] + a[y1 + 1][x1];
					if (a2 < a1) {
						s[y1 + 1][x1] = min(a1, a2);
						paths[y1 + 1][x1] = paths[y1][x1];
						paths[y1 + 1][x1].push_back({ y1, x1 });
						//paths[y1][x1].clear();
					}
					else if (a1 == a2) {
						for (int i = 0; i < paths[y1][x1].size(); i++) {
							paths[y1 + 1][x1].push_back(paths[y1][x1][i]);
						}
						paths[y1 + 1][x1].push_back({ y1, x1 });
						//paths[y1][x1].clear();
					}
				}
				else {
					s[y1 + 1][x1] = s[y1][x1] + a[y1 + 1][x1];
					paths[y1 + 1][x1] = paths[y1][x1];
					paths[y1 + 1][x1].push_back({ y1, x1 });
					//paths[y1][x1].clear();
					queue.push({ y1 + 1, x1 });
				}
			}
			if (x1 < a[0].size() - 1) {
				if (s[y1][x1 + 1] != 0) {
					int a1 = s[y1][x1 + 1];
					int a2 = s[y1][x1] + a[y1][x1 + 1];
					if (a2 < a1) {
						s[y1][x1 + 1] = min(a1, a2);
						paths[y1][x1 + 1] = paths[y1][x1];
						paths[y1][x1 + 1].push_back({ y1, x1 });
						//paths[y1][x1].clear();
					}
					else if (a1 == a2) {
						for (int i = 0; i < paths[y1][x1].size(); i++) {
							paths[y1][x1 + 1].push_back(paths[y1][x1][i]);
						}
						paths[y1][x1 + 1].push_back({ y1, x1 });
						//paths[y1][x1].clear();
					}
				}
				else {
					s[y1][x1 + 1] = s[y1][x1] + a[y1][x1 + 1];
					paths[y1][x1 + 1] = paths[y1][x1];
					paths[y1][x1 + 1].push_back({ y1, x1 });
					//paths[y1][x1].clear();
					queue.push({ y1, x1 + 1 });
				}
			}
			//paths[y1][x1].clear();
		}
		optimal = s;
		op = optimal[n - 1][k - 1];
		oppath = paths[n - 1][k - 1];
	}

	for (int i = 0; i < oppath.size(); i++) {
		int y = oppath[i].first;
		int x = oppath[i].second;
		if ((x != 0 || y != 0) && mem[y][x] == 0) {
			mem[y][x] = 1;
		}
	}

	int q;
	std::cin >> q;
	for (int v = 0; v < q; v++) {
		int x, y;
		std::cin >> y >> x;
		x--;
		y--;

		if (mem[y][x] == 0) {
			std::cout << op << std::endl;
		}
		else {
			if (res[y][x] == 0) {
				res[y][x] = eval(x, y, a, n, k);
				std::cout << res[y][x] << std::endl;
			}
			else {
				std::cout << res[y][x] << std::endl;
			}
		}

	}

	return 0;
}