#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) x.begin(), x.end()
#define pf push_front
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define sz(x) (int)x.size()
#define f first
#define s second
#define mod 1000000007
#define inf 1e9
#define linf 1e18
// const int mod = 998244353;
// OVERFLOW!!!!!!!!!!!!!!!!!!

int main()
{
   ios_base::sync_with_stdio(false);
   cout.tie(nullptr);
   cin.tie(nullptr);
   int n, m;
   cin >> n >> m;
   ll a[n][m];
   for (int i = 0; i < n; i++)
      for (int j = 0; j < m; j++)
         cin >> a[i][j];
   ll dp[n][m];
   dp[n - 1][m - 1] = a[n - 1][m - 1];
   for (int i = m - 2; i >= 0; i--)
      dp[n - 1][i] = dp[n - 1][i + 1] + a[n - 1][i];
   for (int i = n - 2; i >= 0; i--)
      dp[i][m - 1] = dp[i + 1][m - 1] + a[i][m - 1];
   for (int i = n - 2; i >= 0; i--)
      for (int j = m - 2; j >= 0; j--)
         dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) + a[i][j];
   // dp[i][j], najkraci put od polja i, j do polja n, n
   ll dp1[n][m];
   dp1[0][0] = a[0][0];
   for (int i = 1; i < m; i++)
      dp1[0][i] = dp1[0][i - 1] + a[0][i];
   for (int i = 1; i < n; i++)
      dp1[i][0] = dp1[i - 1][0] + a[i][0];
   for (int i = 1; i < n; i++)
      for (int j = 1; j < m; j++)
         dp1[i][j] = min(dp1[i][j - 1], dp1[i - 1][j]) + a[i][j];
   // dp1[i][j], najkraci put od polja 1 1 do polja i, j
   ll precalc[n][m], precalc1[n][m];
   for (int i = 0; i < n; i++)
   {
      for (int j = 0; j < m; j++)
      {
         if (i == n - 1 && j == m - 1)
            precalc[i][j] = dp1[i][j];
         else if (j == m - 1)
            precalc[i][j] = dp1[i][j] + dp[i + 1][j];
         else if (i == n - 1)
            precalc[i][j] = dp1[i][j] + dp[i][j + 1];
         else
            precalc[i][j] = min(dp[i + 1][j], dp[i][j + 1]) + dp1[i][j];
      }
   }
   ll mn1[n][m], mn2[n][m];
   // mn1-od gore desno do dole levo, mn2-od dole levo do gore desno
   mn1[0][m - 1] = precalc[0][m - 1];
   for (int i = m - 2; i >= 0; i--)
      mn1[0][i] = min(precalc[0][i], mn1[0][i + 1]);
   for (int i = 1; i < n; i++)
      mn1[i][m - 1] = min(precalc[i][m - 1], mn1[i - 1][m - 1]);
   for (int i = 1; i < n; i++)
      for (int j = m - 2; j >= 0; j--)
         mn1[i][j] = min({mn1[i - 1][j], mn1[i][j + 1], precalc[i][j]});
   mn2[n - 1][0] = precalc[n - 1][0];
   for (int i = n - 2; i >= 0; i--)
      mn2[i][0] = min(precalc[i][0], mn2[i + 1][0]);
   for (int i = 1; i < m; i++)
      mn2[n - 1][i] = min(precalc[n - 1][i], mn2[n - 1][i - 1]);
   for (int i = n - 2; i >= 0; i--)
      for (int j = 1; j < m; j++)
         mn2[i][j] = min({precalc[i][j], mn2[i + 1][j], mn2[i][j - 1]});
   int q;
   cin >> q;
   while (q--)
   {
      int x, y;
      cin >> x >> y;
      --x, --y;
      if (x == 0 || y == m - 1)
         cout << mn2[x + 1][y - 1] << "\n";
      else if (x == n - 1 || y == 0)
         cout << mn1[x - 1][y + 1] << "\n";
      else
         cout << min(mn1[x - 1][y + 1], mn2[x + 1][y - 1]) << "\n";
   }
   return 0;
}