// Naive approach: Find shortest path from first top segment and then shortest
// path from second top segment to any vertex along that shortest path.

import java.util.*;
import java.io.*;

class Edge {
  public int from,to,cost;

  public Edge(int from, int to, int cost) {
    this.from = from; this.to = to; this.cost = cost;
  }
}

class Node {
  public int id;
  public int dist, parent;
  public ArrayList<Integer> nbr;

  public Node(int id) {
    this.id = id;
    dist = Integer.MAX_VALUE/2;
    parent = -1;
    nbr = new ArrayList<Integer>();
  }
}

public class RSRNaive {
  public static BufferedReader in;
  public static int w,h;
  public static int maxV;
  public static int[][] table;
  public static Node[] graph;
  public static ArrayList<Integer> top;
  public static boolean visited[];
  public static int numv[];
  public static int src, sink;
  public static PriorityQueue<Node> pq;

  public static void main(String[] args) throws IOException {
    try {
      in = new BufferedReader(new InputStreamReader(System.in));
      String line = in.readLine();
      StringTokenizer st = new StringTokenizer(line);
      h = Integer.parseInt(st.nextToken());
      w = Integer.parseInt(st.nextToken());

      table = new int[h][w];
      maxV = 0;
      for (int i = 0; i < h; i++) {
        line = in.readLine();
        st = new StringTokenizer(line);
        for (int j = 0; j < w; j++) {
          // subtract 1 from all inputs to get zero-based:
          table[i][j] = Integer.parseInt(st.nextToken()) - 1;
          maxV = Math.max(maxV,table[i][j]+1);
        }
      }
    } catch(IOException e) {
      System.err.println(e);
    }

    maxV += 2; // "+2" for source (graph[maxV-2]) and sink (graph[maxV-1])
    boolean used[] = new boolean[maxV]; // so we don't duplicate nodes
    Arrays.fill(used,false);
    graph = new Node[maxV];
    src = maxV-2;
    sink = maxV-1;
    graph[src] = new Node(src);
    graph[sink] = new Node(sink);
    // create the graph:
    for (int i = 0; i < h; i++) {
      for (int j = 0; j < w; j++) {
        int t = table[i][j];
        int below;
        if (i < h-1) {
          below = table[i+1][j];
        }
        else {
          below = sink; // goes to "sink" node
        }
        if (!used[t]) {
          graph[t] = new Node(t);
          used[t] = true;
        }
        if (t != below && !graph[t].nbr.contains(below)) {
          graph[t].nbr.add(below);
        }
      }
    }

    // Point the source to the top table element(s):
    graph[src].nbr.add(table[0][0]);
    if (table[0][w-1] != table[0][0]) {
      graph[src].nbr.add(table[0][w-1]);
    }

    int numtop = graph[src].nbr.size();
    pq = new PriorityQueue<Node>(new Comparator<Node>() {
           public int compare(Node x, Node y) {
             return x.dist-y.dist;
           }
         });

    visited = new boolean[maxV];
    reset();
    graph[src].dist = 0;
    dijk(src,src,sink,"");

    // Easy case: only one top piece
    if (numtop == 1) {
       System.out.println(graph[sink].dist-1);

     } else {

      // Hard(er) case: two top pieces. First, get the list of all the
      // vertices along the shortest path; the first one will be
      // one of the two top pieces of the table.
      int short1 = graph[sink].dist-1;

      ArrayList<Integer> path = new ArrayList<Integer>();
      path.add(sink);
      int p = graph[sink].parent;
      while (p >= 0) {
        path.add(p);
        p = graph[p].parent;
      }

      // Now find where a shortest path from the other top piece meets
      // this path; take min over all such and add to the other path
      int start = graph[src].nbr.get(0);
      if (path.get(path.size()-2) == graph[src].nbr.get(0))
        start = graph[src].nbr.get(1);
      reset();
      graph[start].dist = 0;
      dijk(src,start,sink,"");
      int best = Integer.MAX_VALUE;
      for (Integer i: path) {
        best = Math.min(best,short1+graph[i].dist);
      }
      System.out.println(best);
     }
   }

  public static void dijk(int src, int start, int sink, String ind) {
    visited[start] = true;
    Node s = graph[start];
    for (int e: s.nbr) {
      if (visited[e]) continue; // already done
      Node t = graph[e];
      if (s.dist + 1 < t.dist) {
        t.dist = s.dist + 1;
        t.parent = start;
        pq.remove(t);
        pq.add(t);
      }
    }
    if (!pq.isEmpty()) {
      dijk(src,pq.poll().id, sink,ind+"  ");
    }
  }

  public static void reset() {
    pq.clear();
    for (int i = 0; i < maxV; i++) {
      graph[i].dist = Integer.MAX_VALUE/2;
      graph[i].parent = -1;
      visited[i] = false;
    }
  }
}