시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 512 MB131453846.341%

문제

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

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

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

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

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

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

입력

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

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

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

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

출력

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

예제 입력 1

5
1 3 2 0 9
2 0 4 4 3
5 3 -1 1 1
3 7 2 0 1
1 2 3 5 0

예제 출력 1

16

1번 예제의 경우 다음과 같은 이동으로 최소 비용을 구할 수 있다.

  1. (3,3)에서 (2,2)로 이동 -> 3의 비용 소요
  2. (2,2)에서 (1,4)로 이동 -> 5의 비용 소요
  3. (1,4)에서 (4,4)로 이동 -> 5의 비용 소요
  4. (4,4)에서 (5,5)로 이동 -> 1의 비용 소요
  5. (5,5)에서 (3,3)로 이동 -> 2의 비용 소요

따라서 최소 비용은 16이다.

예제 입력 2

5
1 3 2 4 9
2 2 4 4 3
5 3 -1 1 1
3 7 2 7 1
1 2 3 5 9

예제 출력 2

0