경제적인 일방통행 도로

RUN 나라에는 $N$개의 도시가 있고, 일부 도시 사이는 양방향 도로로 연결되어 있다. 각 도로는 서로 다른 두 도시를 잇고, 같은 도시 쌍을 잇는 도로는 두 개 이상 없다. 모든 도시가 도로를 따라 서로 갈 수 있다는 보장은 없다.

교통 문제 때문에 RUN의 시장은 모든 도로를 일방통행으로 바꾸기로 했다. 방향을 정한 뒤에도 어느 도시에서든 다른 모든 도시로 한 개 이상의 도로를 따라 이동할 수 있어야 한다. 시장은 비용을 최대한 아끼려고 이 조건을 만족하는 방향 설정 중 비용이 가장 작은 것을 고른다. 도로의 방향을 정하는 비용은 도로 자체와 그 도로가 향하는 방향에 따라 달라진다.

첫 줄에 도시의 수 $N$이 주어진다. ($2 \leq N \leq 18$)

이어지는 $N$개 줄에는 각각 공백으로 구분된 정수 $N$개가 주어진다. $(i+1)$번째 줄의 $j$번째 정수 $a_{ij}$는 도시 $i$에서 도시 $j$로 향하도록 도로를 정할 때의 비용이다. 두 도시 사이에 도로가 없으면 $-1$이다.

모든 $i$에 대해 $a_{ii} = -1$이다. 서로 다른 두 도시 $i$, $j$에 대해 $a_{ij} = a_{ji} = -1$이거나, $0 \leq a_{ij}, a_{ji} \leq 10^6$이다.

모든 도로의 방향을 조건을 만족하도록 정했을 때 필요한 최소 비용을 출력한다. 조건을 만족하는 방향 설정이 불가능하면 $-1$을 출력한다.