#include using namespace std; typedef long long ll; typedef vector< int > vi; typedef vector< vi > vvi; typedef vector< ll > vl; typedef vector< vl > vvl; typedef pair< int, int > pii; typedef vector< pii > vp; typedef vector< double > vd; typedef vector< vd > vvd; typedef vector< string > vs; template< class T1, class T2 > int upmin( T1 &x, T2 v ){ if( x > v ){ x = v; return 1; } return 0; } template< class T1, class T2 > int upmax( T1 &x, T2 v ){ if( x < v ){ x = v; return 1; } return 0; } const int INF = 0x3f3f3f3f; int N, V, Sx, Sy, Gx, Gy; vvi LV; void init(){ cin >> N >> V >> Sx >> Sy >> Gx >> Gy; --Sx, --Sy, --Gx, --Gy; swap( Sx, Sy ), swap( Gx, Gy ); LV = vvi( N, vi( N ) ); for( int i = 0; i < N; ++i ) for( int j = 0; j < N; ++j ) cin >> LV[ i ][ j ]; } int dis[ 1800 ][ 100 ][ 100 ]; void preprocess(){ memset( dis, INF, sizeof( dis ) ); typedef tuple< int, int, int, int > t4i; queue< t4i > que; que.emplace( dis[ V ][ Sx ][ Sy ] = 0, V, Sx, Sy ); while( not que.empty() ){ int d, v, x, y; tie( d, v, x, y ) = que.front(); que.pop(); if( dis[ v ][ x ][ y ] != d ) continue; if( x == Gx and y == Gy ) cout << d << endl, exit( 0 ); const int dx[] = { 0, 1, 0, -1 }; const int dy[] = { 1, 0, -1, 0 }; for( int di = 0; di < 4; ++di ){ int nx = x + dx[ di ]; int ny = y + dy[ di ]; if( not ( 0 <= nx and nx < N and 0 <= ny and ny < N ) ) continue; if( v - LV[ nx ][ ny ] <= 0 ) continue; if( upmin( dis[ v - LV[ nx ][ ny ] ][ nx ][ ny ], dis[ v ][ x ][ y ] + 1 ) ) que.emplace( dis[ v - LV[ nx ][ ny ] ][ nx ][ ny ], v - LV[ nx ][ ny ], nx, ny ); } } cout << -1 << endl; } void solve(){ } signed main(){ ios::sync_with_stdio( 0 ); init(); preprocess(); solve(); return 0; }