noname57

#include<bits/stdc++.h>
// #include<time.h>
// #include<stdio.h>
// #include<windows.h>
// #include<conio.h>


using namespace std;


typedef bool bul;
typedef char ja;
typedef short sot;
typedef long long ll;
typedef long double ld;
typedef string sj;
#define pe pair
typedef pe<int, int> pii;
#define vec vector
#define fus first
#define sec second
#define MOD (1000000007)
#define PI (2*acos(0))
#define pb push_back


#define FOR(i, a, b) for(ll i = (a); i <= (b); ++i)
#define FORn(i, a, b) for(ll i = (a); i < (b); ++i)
#define FORx(i, a, b, x) for(ll i = (a); i <= (b); i += (x))
#define FORnx(i, a, b, x) for(ll i = (a); i < (b); i += (x))
#define FORR(i, a, b) for(ll i = (a); i >= (b); --i)
#define FORRn(i, a, b) for(ll i = (a); i > (b); --i)
#define FORRx(i, a, b, n) for(ll i = (a); i >= (b); i -= (x))
#define FORRnx(i, a, b, n) for(ll i = (a); i > (b); i -= (x))


#define all(x) (x).begin(), (x).end()
#define sz(x) 1ll*(x).size()
#define sqr(x) (x)*(x)


    /* ----------------- useful func ----------------- */



/* ----------------- ~~~~~~~~~~~ ----------------- */







        /* ----------------- ~~~~~~~ ----------------- */

    int m, n, res = INT_MAX;
    int a[1000][1000];

/* ----------------- ~~~~~~~ ----------------- */

int main(){

    //freopen(".inp", "r", stdin);
    //freopen(".out", "w", stdout);
    //ios_base::sync_with_stdio(0); cin.tie(0);

        /* ----------------- main func ----------------- */

    cin >> m >> n;
    FORn(i, 0, m)
        FORn(j, 0, n){
            cin >> a[i][j];
            if(i == 0) continue;
            int t = a[i - 1][j];
            if(j != 0) t = min(t, a[i - 1][j - 1]);
            if(j != n - 1) t = min(t, a[i - 1][j + 1]);
            a[i][j] += t;
        }
    FORn(i, 0, n)
        res = min(res, a[m - 1][i]);
    cout << res;

/* ----------------- ~~~~~~~~~ ----------------- */

}