# include < iostream >
# include < fstream >
using namespace std ;
const int max_dim = 100 ;
int main () {
ifstream fin ( "date_intrare.txt" ) ;
int n, m;
fin >> n >> m;
int harta[ max_dim ][ max_dim ];
for ( int i = 0 ; i < n; i++) {
for ( int j = 0 ; j < m; j++) {
fin >> harta[i][j];
}
}
fin. close ();
int dp [ max_dim ][ max_dim ] = { 0 };
for ( int j = 0 ; j < m; j++) {
dp [ 0 ][j] = harta[ 0 ][j];
}
for ( int i = 1 ; i < n; i++) {
for ( int j = 0 ; j < m; j++) {
int min_urcare = INT_MAX;
int dx[] = { -1 , 0 , 1 , -1 , 1 };
int dy [] = { -1 , -1 , -1 , 0 , 0 };
for ( int k = 0 ; k < 5 ; k++) {
int prev_i = i + dy [k];
int prev_j = j + dx[k];
if ( prev_i >= 0 && prev_j >= 0 && prev_j < m) {
min_urcare = min ( min_urcare , dp [ prev_i ][ prev_j ] + harta[i][j] - harta[ prev_i ][ prev_j ]);
}
}
dp [i][j] = min_urcare ;
}
}
int min_total = INT_MAX;
for ( int j = 0 ; j < m; j++) {
min_total = min ( min_total , dp [n - 1 ][j]);
}
cout << "Urcare minima: " << min_total << endl ;
return 0 ;
}