Tý là một thương lái chuyên đi thu mua nông sản ở các làng quê trong huyện. Quê hương Tý có đúng \(N\) ngôi làng, các làng được đánh số từ \(0\) đến \(N-1\). Giữa hai làng \(i\) và \(j\) có một con đường với chi phí di chuyển là \(c_{i,j}\) (có thể khác nhau theo chiều đi). Mỗi mùa, Tý xuất phát từ kho ở làng \(0\) và cần đi qua đúng một lần tất cả \(N\) làng để thu mua, cuối cùng nghỉ chân tại một làng bất kỳ trong số các làng đã đi qua để nghỉ ngơi. Hãy tìm cho Tý một hành trình có tổng chi phí nhỏ nhất.

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

• Dòng đầu chứa số nguyên dương \(N\) (\(1 \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\)).

Định dạng đầu ra

• In ra một số nguyên duy nhất là tổng chi phí nhỏ nhất của hành trình bắt đầu từ làng \(0\), đi qua mỗi làng còn lại đúng một lần, kết thúc ở một làng bất kỳ.

Ví dụ

Input:

3
0 10 15
10 0 20
15 20 0

Output:

25

Giải thích: Đi theo hành trình \(0 \to 1 \to 2\) với tổng chi phí \(10 + 20 = 25\).

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.