Cô Mai phụ trách tuyến xe buýt đưa đón học sinh ở một vùng nông thôn rộng lớn. Trong huyện có \(N\) điểm dừng (làng và trường), được đánh số từ \(0\) đến \(N-1\). Mỗi cặp điểm dừng \(i, j\) có quãng đường di chuyển \(c_{i,j}\) (có thể đối xứng \(c_{i,j} = c_{j,i}\)). Sáng nay, cô xuất phát từ trường học ở điểm \(0\), cần đón học sinh ở đúng một lần tại tất cả \(N\) điểm dừng còn lại, rồi quay trở lại điểm \(0\) để kết thúc hành trình. Hãy giúp cô Mai chọn một hành trình có tổng quãng đường nhỏ nhất.

Định dạng đầu vào

• Dòng đầu chứa số nguyên dương \(N\) (\(2 \le N \le 15\)).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa \(N\) số nguyên không âm \(c_{i,0}, c_{i,1}, \ldots, c_{i,N-1}\) (\(0 \le c_{i,j} \le 10^3\), đặc biệt \(c_{i,i} = 0\), dữ liệu đối xứng \(c_{i,j} = c_{j,i}\)).

Định dạng đầu ra

• In ra một số nguyên duy nhất là tổng quãng đường nhỏ nhất của toàn tuyến (bắt đầu từ \(0\), đi qua mọi nơi đúng một lần, kết thúc tại \(0\)).

Ví dụ

Input:

3
0 10 15
10 0 20
15 20 0

Output:

45

Giải thích: Hành trình \(0 \to 1 \to 2 \to 0\) có tổng \(10 + 20 + 15 = 45\).

Ràng buộc

• \(20\%\) số điểm ứng với \(N \le 8\).
• \(30\%\) số điểm ứng với \(N \le 12\).
• \(50\%\) số điểm còn lại không có ràng buộc gì thêm.