TSP

$1$부터 $N$까지 번호가 붙은 $N$개의 도시가 있다.

서로 다른 두 도시 사이를 이동할 때 필요한 비용이 주어진다.

$1$번 도시에서 출발하여 모든 도시를 정확히 한 번씩 방문한 뒤 다시 $1$번 도시로 돌아오려고 한다.

필요한 비용의 최솟값을 구하라.

첫 번째 줄에 도시의 개수 $N$이 주어진다. $(1 \leq N \leq 17)$

두 번째 줄부터 $N$개의 줄에 걸쳐 도시 사이의 이동 비용이 주어진다.

$i$번째 줄의 $j$번째 정수 $C_{i,j}$는 $i$번 도시에서 $j$번 도시로 이동할 때 필요한 비용을 의미한다.

$i=j$라면 $C_{i,j}=0$이고, $i \neq j$라면 $1 \leq C_{i,j} \leq 10^9$이다.

$1$번 도시에서 출발하여 모든 도시를 정확히 한 번씩 방문한 뒤 다시 $1$번 도시로 돌아올 때 필요한 비용의 최솟값을 출력한다.