#include<bits/stdc++.h>
#define int long long
using namespace std;
const int oo =1e18;

int m, n;
int a[505][505];
int dp[505][505];

main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>m>>n;
    for (int i=1;i<=m;i++)
    {
        for (int j=1;j<=n;j++)
        {
            cin>>a[i][j];
        }
    }

    for (int i=0;i<=m+1;i++)
    {
        for (int j=0;j<=n+1;j++)
        {
            dp[i][j]=oo;
        }
    }

    for (int i=1;i<=m;i++)
    {
        dp[i][1] = a[i][1];
    }

    for (int j =2;j<=n;j++)
    {
        for (int i = 1;i<=m;i++)
        {
            int res = min({dp[i-1][j-1], dp[i][j-1], dp[i+1][j-1]});
            dp[i][j] = res+ a[i][j];
        }
    }

    int ans =oo;
    for (int i =1;i<=m;i++)
    {
        ans =min(ans, dp[i][n]);
    }

    cout<<ans;
}