1번부터 \(N\)번까지 번호가 붙어 있는 \(N\)개의 도시가 있다. 도시들 사이에는 길이 있을 수도 있고 없을 수도 있으며, 각 길을 지나갈 때 드는 비용이 다를 수 있다.

한 외판원이 어느 한 도시에서 출발하여 \(N\)개의 모든 도시를 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다.

단, 한 번 방문했던 도시로는 다시 갈 수 없다. (맨 마지막에 출발했던 도시로 돌아오는 것은 예외)

각 도시 간의 이동 비용이 행렬 \(W[i][j]\) 형태로 주어진다. \(W[i][j]\)는 도시 \(i\)에서 도시 \(j\)로 가기 위한 비용을 나타낸다.

비용은 대칭적이지 않을 수 있다. 즉, \(W[i][j]\)와 \(W[j][i]\)는 다를 수 있다. 도시 \(i\)에서 도시 \(j\)로 갈 수 없는 경우 \(W[i][j] = 0\)으로 주어진다.

\(N\)개의 도시를 모두 순회하는 데 드는 최소 비용을 구하는 프로그램을 작성하시오. 항상 순회 가능한 경로가 존재하는 입력만 주어진다.

입력

첫째 줄에 도시의 개수 \(N\)이 주어진다. (\(2 \le N \le 16\)) 둘째 줄부터 \(N\)개의 줄에 걸쳐 각 도시 간의 이동 비용을 나타내는 \(N \times N\) 행렬이 주어진다.

• 각 행렬의 성분은 \(0\) 이상 \(1,000,000\) 이하의 정수이다.
• 자기 자신으로 가는 비용 \(W[i][i]\)는 항상 \(0\)이다.

출력

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

예제 입력 1

4
0 10 15 20
5 0 9 10
6 13 0 12
8 8 9 0

예제 출력 1

35