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

namespace ConsoleApp29
{
    internal class Program
    {
        static void Main(string[] args)
        {
            string[] rec = Console.ReadLine().Split();
            int n = int.Parse(rec[0]);
            int m = int.Parse(rec[1]);
            int[,] doha = new int[n, m];
            int[,] tren = new int[n, m];
            for (int i = 0; i < n; i++)
            {
                rec = Console.ReadLine().Split();
                for (int j = 0; j < m; j++)
                {
                    doha[i, j] = int.Parse(rec[j]);
                    tren[i, j] = int.MaxValue;
                }
            }
            int u = int.Parse(Console.ReadLine());
            int[,] skr = new int[u, 2];
            for (int i = 0; i < u; i++)
            {
                rec = Console.ReadLine().Split();
                skr[i, 0] = int.Parse(rec[0]) - 1;
                skr[i, 1] = int.Parse(rec[1]) - 1;
            }
            tren[0, 0] = doha[0, 0];
            HashSet<string> plavi = new HashSet<string>();
            for (int i = 0; i < u; i++)
            {
                int zb = 0;
                plavi.Clear();
                plavi.Add(0 + "," + 0);
                while (!plavi.Contains((n - 1) + "," + (m - 1)) || plavi.Count == 0)
                {
                    zb = int.MaxValue;
                    int[] q = new int[2];
                    foreach (string cor in plavi.ToHashSet<string>())
                    {
                        string[] h = cor.Split(',') ;
                        int x = int.Parse(h[0]); int y = int.Parse(h[1]);

                        if ((plavi.Contains((x + 1) + "," + y) && plavi.Contains((x + 1) + "," + y)) || x + 1 == n && y + 1 == m) { plavi.Remove(x + "," + y); continue; }
                        if (!plavi.Contains((x + 1) + "," + y) && (skr[i, 0] != x + 1 || skr[i, 1] != y) && x + 1 != n && tren[x, y] + doha[x + 1, y] < zb) { zb = tren[x, y] + doha[x + 1, y]; q = new int[] { x + 1, y }; }
                        if (!plavi.Contains(x + "," + (y + 1)) && (skr[i, 0] != x || skr[i, 1] != y + 1) && y + 1 != m && tren[x, y] + doha[x, y + 1] < zb) { zb = tren[x, y] + doha[x, y + 1]; q = new int[] { x, y + 1 }; }
                    }
                    plavi.Add(q[0] + "," + q[1]);
                    tren[q[0], q[1]] = zb;
                }
                Console.WriteLine(zb);
            }
            


        }
    }
}