철도 노선 건설

MRT 사가 전국에 철도를 놓는 일을 맡아 여러분을 채용했다.

지도는 한 변이 $N$인 정사각형 격자다. 각 칸에는 그 칸에 사는 주민 수 $C$가 적혀 있다. 철도가 지나가는 칸의 주민은 모두 이주해야 하므로, 두 역 $A$와 $B$를 잇는 노선 가운데 이주 인원이 가장 적은 노선을 골라 그 인원을 구한다. 지반이 불안정하거나 언덕이 있어 철도를 놓을 수 없는 칸도 있다.

철도는 대각선으로 놓을 수 없고 상하좌우 네 방향으로만 이어진다. 노선은 역 $A$가 있는 칸에서 시작해 역 $B$가 있는 칸에서 끝나고, 두 역이 있는 칸도 노선에 포함된다. 이주 인원은 노선이 지나는 모든 칸의 주민 수를 더한 값이다.

첫째 줄에 지도의 한 변 길이 $N$이 주어진다. ($2 \le N \le 400$)

둘째 줄에 네 정수 $A_x$, $A_y$, $B_x$, $B_y$가 주어진다. 차례대로 역 $A$의 $x$좌표와 $y$좌표, 역 $B$의 $x$좌표와 $y$좌표다. $x$는 왼쪽에서부터, $y$는 위에서부터 센다. 두 역의 위치는 서로 다르다. ($1 \le A_x, A_y, B_x, B_y \le N$)

셋째 줄부터 $N$개의 줄에 걸쳐 각 줄에 $N$개의 정수 $C$가 공백으로 구분되어 주어진다. 위에서 $i$번째 줄의 $j$번째 수는 $x$좌표가 $j$이고 $y$좌표가 $i$인 칸의 값이다. 철도를 놓을 수 없는 칸은 $-1$로 주어진다. ($-1 \le C \le 10^6$)

이주해야 하는 주민 수의 최솟값을 한 줄에 출력한다.

철도를 놓을 수 없는 칸을 지나지 않고는 두 역을 이을 수 없으면 $-1$을 출력한다. 두 역 중 한 곳이라도 철도를 놓을 수 없는 칸에 있으면 노선을 만들 수 없으므로 이때도 $-1$을 출력한다.