외판원 문제 (소규모)

N개의 도시가 있다. 도시 i에서 도시 j로 이동하는 비용이 주어진다. 도시 1에서 출발하여 모든 도시를 정확히 한 번씩 방문하고 도시 1로 돌아오는 최소 비용을 구하라.

입력

첫째 줄에 도시의 수 N이 주어진다.
이후 N개의 줄에 N개의 정수가 주어진다. i행 j열의 값이 i→j 이동 비용이다. 대각선 값은 0이다.

• 2 ≤ N ≤ 16
• 0 ≤ 이동 비용 ≤ 1,000,000 (0이면 해당 경로 없음, 항상 해를 구할 수 있는 입력이 주어짐)

출력

모든 도시를 순회하는 최소 비용을 출력한다.

예제 입력 1

4
0 10 15 20
10 0 35 25
15 35 0 30
20 25 30 0

예제 출력 1

80