1186번: 외판원의 최소 한 바퀴

도시 N개를 모두 한 번씩 방문하고 출발 도시로 돌아오는 최소 비용을 구하세요. 도시가 많아서 방문 순서를 전부 따져 보면 너무 느려요. 도시 i에서 j로 가는 비용이 표로 주어져요. 비용이 0이면 그 길은 없는 거예요.

입력

첫째 줄에 N이 주어져요. (2 ≤ N ≤ 16) 다음 N줄에 비용 표가 주어져요. (0 ≤ 비용 ≤ 10,000, 한 바퀴 도는 방법은 항상 있어요)

출력

최소 비용을 출력해요.