23354번 - 군탈체포조

문제

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

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

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

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

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

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

입력

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

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

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

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

출력

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

제한

노트