Deserter Pursuit

The Deserter Pursuit (DP) is a unit of soldiers who track down and arrest deserters.

One day, Hoyul, a member of the Deserter Pursuit, is given operating funds and a map, along with orders to catch all the deserters and return to base. Hoyul wants to save money to buy bagged ramen, so he tries to catch all the deserters while spending as little of the operating funds as possible.

The map is an $N \times N$ grid. The positions of the base and the deserters are given on the map, and every other cell that does not contain the base or a deserter contains a tollgate.

Each tollgate has a fixed toll, and to visit a cell with a tollgate, Hoyul must pay the toll. Also, visiting the same cell multiple times requires paying the toll each time.

Hoyul must start at the base, catch all the deserters, and return, and he may stop by the base in the middle. He can move one cell at a time to an adjacent cell up, down, left, or right, and he cannot go anywhere other than the spaces shown on the map.

For Hoyul, who wants to do nothing, compute the minimum cost to start at the base, catch all the deserters, and return to the base.

The first line gives the size of the grid $N$. ($5 \le N \le 1,000$)

The next $N$ lines give the map. $-1$ is the base, $0$ is a deserter, and an integer of $1$ or more is the toll of a tollgate; every toll is an integer of $1,000$ or less.

The input contains exactly one base, and the number of deserters is at most 5.

There may be no deserters.

On the first line, output the answer to the problem.