해밀턴 - 뮤지컬

네를로니아는 튼튼한 도로망으로 유명하다. 이 나라에는 1번부터 $N$번까지 번호가 붙은 도시 $N$개가 있고, 서로 다른 두 도시 $i$, $j$마다 길이가 $L_{i,j}$인 양방향 도로가 하나씩 있다. 네를로니아 시민들은 뮤지컬 해밀턴이 처음으로 이 나라에 온다는 소식에 들떠 있다. 주최 측은 모든 시민이 공연을 볼 기회를 얻기를 바라므로, 각 도시를 정확히 한 번씩 방문하는 경로를 원한다. 이런 경로는 $N$개 도시의 순열 $P_1, P_2, \dots, P_N$이며, 경로의 총 길이는 $\sum_{i=1}^{N-1} L_{P_i,P_{i+1}}$이다.

주최 측은 배우들이 경로를 고르면 연료비가 많이 들까 걱정한다. 반대로 배우들에게 아무것도 고르게 하지 않으면 의욕이 떨어져 무대 공연이 나빠질까 걱정한다. 그래서 짝수 번째 위치의 도시는 배우들이 고르도록 허용했다. 즉 배우들은 $P_2, P_4, \dots, P_{\lfloor N/2 \rfloor}$에 놓일 도시를 고를 수 있다.

배우들은 평범한 결정을 내렸다. 짝수 번째 위치 $i$에 놓는 도시는 번호가 $i$인 도시로 하기로 했다. 즉 모든 짝수 $i$에 대해 $P_i = i$이다. 이 조건을 만족하는 경로의 총 길이 최솟값을 구하라.

첫 줄에 도시의 수 $N$($2 \le N \le 500$)이 주어진다. 이후 $N$개의 줄에 각각 정수 $N$개가 주어지며, $i$번째 줄의 $j$번째 정수는 $L_{i,j}$이다($i \ne j$일 때 $1 \le L_{i,j} = L_{j,i} \le 10^9$). $i = j$이면 도시에서 자기 자신으로 가는 도로가 없으므로 $L_{i,j} = 0$이다.

배우들의 결정을 만족하는 경로의 총 길이 최솟값을 한 줄에 출력한다.