import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Scanner;

// The picture shows an example of 4 rows and 3 columns of hexagons. The numbers represent the height of each tile. The height of the ground outside the hexagons is always 0.

// Pesho has to enter the upper-left tile pass and exit from the bottom-right one. When he passes through two different heights his bike receives damage equal to their difference. Help Pesho minimize the damage his bike receives.
// Input

//     Input is read from the console
//         On the first line an integer number R is given
//             the number of rows
//         On the second line an integer number C is given
//             the number of columns
//         On each of the next R lines C numbers will be given
//             the heights of the tiles
//             separated by spaces

// Output

//     Output should be printed to the console
//     On single line print the minimal the damage Pesho's bike can receive
//         Output with two digits of precision

// Constraints

//     0 < R, C <= 500
//     -100 <= height of a cell <= 100
// Sample Input
// 4
// 3
// 2 3 1
// 5 4 6
// 9 0 3
// 8 5 2

// Pesho enters cell 2  -> receiving 2 damage
// then goes to cell 3  -> receiving 1 damage
// then goes to cell 4  -> receiving 1 damage
// then goes to cell 3  -> receiving 1 damage
// then goes to cell 2  -> receiving 1 damage
// finally exits cell 2 -> receives 2 damage

// total damage -> 8

public class BikeDamage {
    static boolean recursion = false;
    static boolean[] visited = new boolean[50];

    static void path(int source, LinkedList<Edge>[] adj,int B, float[][] matrix,  float maxCount, int R, int C) {

        int count = 0;

        if(source == B) {
            recursion = true;
            System.out.println(maxCount + matrix[R-1][C-1] + matrix[0][0]);
        } else {

            int dest = 0;

            LinkedList<Edge> l = adj[source];
            float min = Integer.MAX_VALUE;
            int minDest = 0;

            for (Edge i : l) {

                if(min > i.weight) {
                    min = i.weight;
                    minDest = i.destination;
                }
            }



            maxCount += min;

            source = minDest;
            path(source, adj, B, matrix, maxCount, R, C);

        }

    }

    public static void main(String args[]) throws IOException  {
        Scanner sc = new Scanner(System.in);
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int R = sc.nextInt();
        int C = sc.nextInt();

        float[][] hexagon = new float[R][C];

        float[] junk = new float[C];

        Graph graph = new Graph(R*C);

        for(int i=0;i < R; i++) {
            String[] in = br.readLine().split(" ");
            for(int k=0; k < C; k++) {

                junk[k] = Float.parseFloat(in[k]);
            }
            for(int j=0; j<C; j++) {
                hexagon[i][j] = junk[j];
            }
        }

        for(int i=0; i<R; i++) {
            for(int j=0; j<C; j++) {
                System.out.print(hexagon[i][j] + " ");
            }
            System.out.println();
        }

        for(int i=0; i<R; i++) {
            for(int j=0; j<C; j++) {
                int currentNode = i * (R - 1) + j;
                // Even Rows / Zero Column
                if (i == R - 1 && j == C - 1) {
                    break;
                }

                    if (j == 0 && i % 2 == 0) {
                        // Right Neighbor
                        graph.addEgde(currentNode, i * (R - 1) + j + 1, Math.abs(hexagon[i][j] - hexagon[i][j + 1]));
                        // Down Neighbor
                        graph.addEgde(currentNode, (i + 1) * (R - 1) + j, Math.abs(hexagon[i][j] - hexagon[i + 1][j]));
                        // Last Column
                    } else if (j == C - 1) {
                        // Down Neighbor
                        graph.addEgde(currentNode, (i + 1) * (R - 1) + j, Math.abs(hexagon[i][j] - hexagon[i + 1][j]));
                        // Diagonal Neighbor
                        graph.addEgde(currentNode, (i + 1) * (R - 1) + (j - 1), Math.abs(hexagon[i][j] - hexagon[i + 1][j - 1]));
                        // Last Row
                    } else if (i == R - 1) {
                        // Right Neighbor
                        graph.addEgde(currentNode, (i) * (R - 1) + j + 1, Math.abs(hexagon[i][j] - hexagon[i][j + 1]));
                        // hexagon inside
                    } else if (i % 2 == 0) {
                        // Right Neighbor
                        graph.addEgde(currentNode, i * (R - 1) + j + 1, Math.abs(hexagon[i][j] - hexagon[i][j + 1]));
                        // Down Neighbor
                        graph.addEgde(currentNode, (i + 1) * (R - 1) + j, Math.abs(hexagon[i][j] - hexagon[i + 1][j]));
                        // Diagonal Neighbor
                        graph.addEgde(currentNode, (i + 1) * (R - 1) + (j - 1), Math.abs(hexagon[i][j] - hexagon[i + 1][j - 1]));

                    } else { // ODD ROWS
                        // Right Neighbor
                        graph.addEgde(currentNode, i * (R - 1) + j + 1, Math.abs(hexagon[i][j] - hexagon[i][j + 1]));
                        // Down Neighbor
                        graph.addEgde(currentNode, (i + 1) * (R - 1) + j, Math.abs(hexagon[i][j] - hexagon[i + 1][j]));
                        // Diagonal Neighbor
                        graph.addEgde(currentNode, (i + 1) * (R - 1) + (j + 1), Math.abs(hexagon[i][j] - hexagon[i + 1][j + 1]));
                    }


            }
        }
        int B = R*C - 1;

        path(0, graph.adjacencylist, B, hexagon,0, R, C);

        System.out.println();


        }
    }