외판원 순회

도시는 1번부터 N번까지 번호가 매겨져 있다. 일부 도시 사이에는 이동할 수 있는 길이 있고, 길이 없는 경우도 있다. 한 외판원이 어떤 도시에서 출발해 모든 도시를 정확히 한 번씩 방문한 뒤 다시 출발 도시로 돌아오는 순회 경로를 계획하려고 한다. 마지막에 출발 도시로 돌아오는 경우만 예외로 하며, 그 외에는 이미 방문한 도시를 다시 방문할 수 없다.

도시 사이의 이동 비용은 행렬 W로 주어진다. W[i][j]는 도시 i에서 도시 j로 이동하는 비용이다. 비용은 방향에 따라 다를 수 있으므로 W[i][j]와 W[j][i]가 같을 필요는 없다. W[i][i]는 항상 0이다. 도시 i에서 도시 j로 이동할 수 없으면 W[i][j]도 0으로 주어진다.

도시의 수 N과 비용 행렬 W가 주어졌을 때, 가능한 순회 경로 중 총비용이 가장 작은 값을 구하라.

첫째 줄에 도시의 수 N이 주어진다. (2 <= N <= 16)

다음 N개의 줄에는 비용 행렬이 주어진다. 각 원소는 이동할 수 있는 경우 1,000,000 이하의 양의 정수이고, 이동할 수 없는 경우 0이다. W[i][j]는 도시 i에서 도시 j로 이동하는 비용을 뜻한다.

항상 순회 경로가 존재하는 입력만 주어진다.

첫째 줄에 외판원의 순회에 필요한 최소 비용을 출력한다.