Train Line Construction

MRT Corp is building railways across the country and has hired you.

The map is a square grid with $N$ cells on each side. Each cell holds the number of residents $C$ who live there. Everyone living on a cell the railway passes through has to move, so you pick the line between station $A$ and station $B$ that forces the fewest residents to move, and report that number. Some cells cannot carry track at all because the ground is unstable or a hill is in the way.

Track cannot run diagonally. It only connects cells up, down, left, and right. The line starts on the cell holding station $A$ and ends on the cell holding station $B$, and both station cells are part of the line. The number of residents who move is the sum of $C$ over every cell the line passes through.

The first line contains $N$, the side length of the map. ($2 \le N \le 400$)

The second line contains four integers $A_x$, $A_y$, $B_x$, $B_y$: the $x$ and $y$ coordinates of station $A$, then the $x$ and $y$ coordinates of station $B$. The $x$ coordinate is counted from the left and the $y$ coordinate from the top. The two stations sit on different cells. ($1 \le A_x, A_y, B_x, B_y \le N$)

Each of the next $N$ lines contains $N$ integers $C$ separated by spaces. The $j$th number on the $i$th of these lines is the value of the cell with $x$ coordinate $j$ and $y$ coordinate $i$. A cell that cannot carry track is given as $-1$. ($-1 \le C \le 10^6$)

Print the smallest number of residents who have to move, on one line.

If the two stations cannot be connected without laying track on a forbidden cell, print $-1$. If either station sits on a forbidden cell, no line can be built, so print $-1$ in that case too.