/* file: side.c */
/* author: Anastase Luca-George (email: l.anastase@student.rug.nl) */
/* date: 10/23/2024 */
/* version: 1.0 */
/* Description: This program prints the minimum-cost path in a grid given some specifications */

#include <stdio.h>

#define NMAX 1005

int n, m;
int mat[NMAX][NMAX];
int dp[NMAX][NMAX];

// Function to return the minimum of two integers
int mini(int x, int y) {
  if(x > y) {
    return y;
  }
  return x;
}

int main(){
  // Read the dimensions of the matrix
  scanf("%d%d", &n, &m);

  // Read the input matrix values
  for(int i = 1; i <= n; ++i) {
    for(int j = 1; j <= m; ++j) {
      scanf("%d", &mat[i][j]);
    }
  }

  // Initialize the DP table with a large value (infinity equivalent)
  for(int i = 0; i <= n + 1; ++i) {
    for(int j = 0; j <= m + 1; ++j) {
      dp[i][j] = 10000000;
    }
  }

  // Base case: Set the last column of dp to the corresponding values in mat
  for(int i = 1; i <= n; ++i) {
    dp[i][m] = mat[i][m];
  }

  // Build the DP table from right to left (from column m-1 to 1)
  for(int j = m - 1; j >= 1; --j) {
    for(int i = 1; i <= n; ++i) {
      dp[i][j] = mini(dp[i+1][j+1], mini(dp[i][j+1], dp[i-1][j+1])) + mat[i][j];
    }
  }

  int min = 10000000;

  // Find the minimum cost starting from the first column
  for(int i = 1; i <= n; ++i) {
    if(dp[i][1] < min) {
      min = dp[i][1];
    }
  }

  // Output the minimum cost
  printf("%d\n", min);
  return 0;
}