영선이는 우편을 배달해주는 집배원이다. 이제 n개의 도시를 전부 방문하여 우편물을 배달해야 하는 업무를 받았다. n개의 도시를 중복없이 돌면서 우편물들을 적절히 배달을 해야 하는데, 영선이는 이 일이 너무 귀찮은 나머지 우편물을 대충 배달하기 시작했다.</p>

영선이는 한 도시를 방문할 때마다 우편물을 하나씩 배달한 후 다른 도시로 이동하며(한 도시에서 한번에 여러 우편물을 배달하면 티가 나므로), 빠르게 일을 마칠 수 있다면 잘 못 배달하더라도 방문한 도시를 또 방문하여 잘못된 우편물을 배달한다. 따라서 여러 번 방문한 도시가 존재하고, 방문하지 않은 도시가 발생한다.

결국 영선이의 만행은 들키고 말았고, 당신은 이 우편물들을 다시 회수해야 한다. 하지만 영선이는 출발지도, 어떻게 이동했는지도 까먹었고, 이동한 거리가 최소로 되게 이동했다는 사실만을 알려줬다.

영선이의 이동경로를 파악하기 위해, 전체 이동이 최소가 되는 경로의 이동 거리를 출력하시오.

입력 형식

첫 줄에는 방문하는 도시 n개가 주어지고(1≤n≤500), 그 다음 n줄에는 n개의 원소가 주어지는 데, i번째 줄의 j번째 원소는 i에서 j로 가는데 거리이다. 만약 거리가 0이면 i에서 j로는 이동할 수 없다. 또한, 두 도시를 잇는 도로가 서로 다른 방향에 대해서 거리가 다를 수 있으며, 일방통행인 경우도 존재한다.</p>

거리는 1보다 크며 100,000보다는 작거나 같다.

출력 형식

도시를 n번 방문하는데 최소가 되는 경로의 이동거리를 출력하시오. 만약 최소가 되는 경로를 찾을 수 없으면 -1을 출력하시오.

예제 입력 1

3
0 1 2
2 0 1
0 1 0

예제 출력 1

2

예제 입력 2

3
0 1 2
0 0 0
0 0 0

예제 출력 2

-1