APTX4869를 만들었던 하이바라는 모든 올림피아드 대회(수학, 정보, 물리, 화학 등)에 참가하고 싶어 했다. 대회에 참가하여 상이란 상은 다 타고 싶은 마음이었지만, 한 가지 걸리는 것이 있었다.

문제는 올림피아드 대회가 모두 전국에서 열리는 관계로 KTX 값이 굉장히 많이 들어간다는 것이다. 결국에는 집으로 다시 돌아와야 하는데, 모든 대회에 1번씩만 참가하고 집으로 돌아오는 경비를 가장 최소화하고 싶다. 하이바라는 이것을 해결하지 못하면, 대회에 참가하기가 어렵게 된다. 대회는 참가하기만 하면 언제든지 문제를 풀 수 있기 때문에 경비를 계산하는 것 이외의 사항은 고려하지 않아도 된다. 하이바라는 부자니까.

입력

• 첫 줄은 참가하는 대회의 수 N(1≤N≤19)을 입력 받는다. 이때, 출발지(집)는 1번으로 한다.
• 둘째 줄은 N X N 크기의 대회 개최지와 개최지를 이동하는 항공료가 나온다. 각 항공료는 한 칸의 공백으로 구분된다. 만약에 개최지에서 개최지로 이동할 수 없는 항공로가 있다면 KTX 승차권의 값을 0으로 표시한다.

출력

입출력 예

입력

5 
0 14 4 10 20 
14 0 7 8 7 
4 5 0 7 16 
11 7 9 0 2 
18 7 17 4 0

출력 

30

출처:algolab.org