군탈체포조

군탈 체포조(Deserter Pursuit)는 탈영병을 추적하고 체포하는 군인을 말하며, 줄여서 DP라고도 한다.

어느 날 군탈 체포조인 호열이에게 활동비와 지도를 주고 탈영병들을 모두 잡아 부대에 복귀하라는 명령이 내려졌다. 돈을 아껴 봉지라면을 사 먹고 싶은 호열이는 활동비를 최대한 아끼면서 탈영병을 모두 잡으려고 한다.

지도는 $N \times N$ 크기의 격자로 표현된다. 지도 위에는 부대와 탈영병들의 위치가 주어지며, 부대나 탈영병이 없는 나머지 칸에는 모두 톨게이트가 존재한다.

각 톨게이트에는 내야 하는 통행료가 정해져 있고, 톨게이트가 있는 칸을 방문하려면 반드시 통행료를 지불해야 한다. 또한 같은 칸을 여러 번 방문해도 매번 통행료를 내야 한다.

호열이는 부대에서 출발해 탈영병을 모두 잡은 후 복귀해야 하며, 중간에 부대를 들러도 상관없다. 단, 한 번에 상하좌우 인접한 곳으로 1칸씩 이동할 수 있고, 지도에 표시된 곳 이외의 공간에는 갈 수 없다.

아무것도 하기 싫은 호열이를 위해 부대에서 출발해 탈영병을 모두 잡은 후 부대로 복귀하는 데 드는 최소 비용을 대신 구해 주자.

첫째 줄에 격자의 크기 $N$이 주어진다. ($5 \le N \le 1,000$)

둘째 줄부터 $N$개의 줄에 지도의 모양이 주어진다. $-1$은 부대, $0$은 탈영병, $1$ 이상의 정수는 톨게이트의 통행료를 의미하며 모든 통행료는 $1,000$ 이하의 정수이다.

단, 입력에서 부대는 1개만 주어지며 탈영병의 수는 5명 이하로 주어진다.

탈영병이 존재하지 않을 수도 있다.

첫째 줄에 문제의 정답을 출력한다.