Problem Statement

Taro is a peddler who walks through the desert.
He is now about to head for the next town.

Some places in the desert are easy to travel through and others are not,
and from his many years of experience, Taro
knows how much stamina he will lose by going to each place.

The desert stretches on without limit, but Taro only knows an area of \( N\times N \) squares,
and since going outside it would put his life in danger, he will never go there.

Taro currently has stamina \(V\) and stands at \( (S_X,S_Y) \), and the next town is at \( (G_X,G_Y) \).
Taro can only move to squares adjacent up, down, left, or right, sharing an edge with his current square.
Moving from his current square to a neighboring square counts as \(1\) move,
and in addition, his stamina decreases by the desert level \( (L_{XY}) \) of the square he moved to.
If the desert level of the destination is \(0\), his stamina does not decrease,
but Taro dies the moment his stamina becomes \(0\) or less.
He must not die at the very moment he arrives at the town, either.

Since Taro wants to sell his goods as soon as possible,
compute how long it takes for him to "reach the next town as fast as possible"
"without dying".

Input

\(N\ V\ S_X\ S_Y\ G_X\ G_Y\)
\( L_{11}\ L_{21}\ L_{31}\ \cdots\ L_{N1} \)
\( L_{12}\ L_{22}\ L_{32}\ \cdots\ L_{N2} \)
\( \cdots \)
\( L_{1N}\ L_{2N}\ L_{3N}\ \cdots\ L_{NN} \)

Line \(1\) contains the integer \( N\ ( 3 \leq N \leq 100 ) \) representing the length of 1 side of the desert,
the integer \( V\ ( 1 \leq V \leq 10000 ) \) representing Taro's stamina,
the pair of integers \( (S_X,S_Y) (1 \leq S_X,S_Y \leq N) \) representing Taro's initial position,
and the pair of integers \( (G_X,G_Y) (1 \leq G_X,G_Y \leq N) \) representing the position of the next town,
separated by spaces.
The following \(N\) lines give the desert level \( L_{XY}\ (0 \leq L_{XY} \leq 9) \) of each place, separated by spaces.

The initial position \((S_X,S_Y)\) and the position of the next town \((G_X,G_Y)\) are never the same coordinates.

Output

Output the minimum number of moves for Taro to reach the next town as fast as possible without dying.
If he cannot arrive alive no matter what, output \(-1\).
Print a newline at the end.

Sample

3 2 1 1 3 1
0 2 0
0 1 0
0 0 0

4

4 25 1 1 4 4
0 1 3 3
1 4 1 5
2 2 7 8
6 7 4 9

-1

21 40 15 1 18 21
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
9 4 3 9 0 4 4 3 0 8 7 0 2 2 2 3 8 1 2 1 2
2 5 6 3 4 9 1 2 2 6 6 8 0 1 1 0 9 8 4 6 3
6 5 0 7 9 9 7 2 9 4 3 0 9 7 5 9 0 4 1 9 5
3 9 2 1 8 4 7 9 8 0 3 9 5 1 2 1 2 5 9 8 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
5 1 7 9 5 2 3 0 4 0 8 4 4 8 5 4 2 8 3 8 6
3 9 6 7 3 0 4 1 9 5 1 2 2 3 0 8 0 6 6 4 4
3 6 6 6 7 4 5 3 0 6 7 3 5 1 9 3 0 5 9 9 9
8 1 1 4 2 5 9 3 2 4 1 8 4 6 3 5 5 3 3 6 4
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
5 5 7 7 9 2 8 4 5 6 4 6 8 2 7 3 5 8 5 2 4
9 0 7 7 0 4 1 6 1 9 1 5 0 1 6 5 2 6 6 6 5
3 9 7 7 2 6 3 7 1 5 3 8 9 5 6 3 4 8 7 3 4
8 9 1 0 3 9 4 3 9 1 4 8 1 0 5 9 4 3 6 1 3
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
9 5 0 0 4 9 3 9 6 5 4 2 1 5 9 8 7 8 8 6 3
7 2 3 9 9 9 7 7 0 5 8 0 6 3 6 1 2 3 1 0 5
7 8 1 1 8 5 4 3 5 0 2 5 8 5 3 5 3 4 1 0 7
7 1 8 1 2 0 5 8 1 3 9 6 1 3 8 3 9 4 8 6 8
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

33