using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace guzva
{
    internal class Program
    {
        static Tuple<long, string> MINput(long[,] a)
        {
            int n = a.GetLength(0);
            int m = a.GetLength(1);
            string[,] s = new string[n, m];
            long[,] a1 = new long[n, m];
            a1[0, 0] = a[0, 0];
            s[0, 0] = "";
            for (int i = 1; i < m; i++)
            {
                a1[0, i] = a1[0, i - 1] + a[0, i];
                s[0, i] = s[0, i - 1] + 'r';
            }
            for (int i = 1; i < n; i++)
            {
                a1[i, 0] = a1[i - 1, 0] + a[i, 0];
                s[i, 0] = s[i - 1, 0] + 'd';
            }
            for (int i = 1; i < n; i++)
                for (int j = 1; j < m; j++)
                {
                    long tr = a1[i - 1, j];
                    string str = s[i - 1, j] + "d";
                    if (a1[i, j - 1] < tr)
                    {
                        tr = a1[i, j - 1];
                        str = s[i, j - 1] + "r";
                    }
                    a1[i, j] = a[i, j] + tr;
                    s[i, j] += str;
                }
            Tuple<long, string> t = new Tuple<long, string>(a1[n - 1, m - 1], s[n - 1, m - 1]);
            return t;
        }
        static long MINput2(long[,] a, int x, int y)
        {
            long pom = a[x, y];
            a[x, y] = int.MaxValue;
            int n = a.GetLength(0);
            int m = a.GetLength(1);
            long[,] a1 = new long[n, m];
            a1[0, 0] = a[0, 0];
            for (int i = 1; i < m; i++)
                a1[0, i] = a1[0, i - 1] + a[0, i];
            for (int i = 1; i < n; i++)
                a1[i, 0] = a1[i - 1, 0] + a[i, 0];
            for (int i = 1; i < n; i++)
                for (int j = 1; j < m; j++)
                {
                    a1[i, j] = Math.Min(a1[i - 1, j], a1[i, j - 1]) + a[i, j];
                }
            a[x, y] = pom;
            return a1[n - 1, m - 1];
        }
        static void Main(string[] args)
        {
            int n, m;
            string[] s = Console.ReadLine().Split();
            n = int.Parse(s[0]);
            m = int.Parse(s[1]);
            long[,] a = new long[n, m];
            for (int i = 0; i < n; i++)
            {
                s = Console.ReadLine().Split();
                for (int j = 0; j < m; j++)
                {
                    a[i, j] = long.Parse(s[j]);
                }
            }
            Tuple<long, string> t = MINput(a);
            long sum = t.Item1;
            string path = t.Item2;
            long[,] a1 = new long[n, m];
            int i1 = 0, l1 = 0;
            for (int i = 0; i < n + m - 3; i++)
            {
                if (path[i] == 'd')
                    i1++;
                else
                    l1++;
                a1[i1, l1] = MINput2(a, i1, l1);

            }
            int q = int.Parse(Console.ReadLine());
            while (q-- > 0)
            {
                s = Console.ReadLine().Split();
                int x = int.Parse(s[0]);
                int y = int.Parse(s[1]);
                long ans = sum;
                if (a1[x - 1, y - 1] != 0)
                    ans = a1[x - 1, y - 1];
                Console.WriteLine(ans);
            }
        }
    }
}