Có ~n~ thành phố. Đi từ thành phố ~i~ tới thành phố ~j~ tốn ~A_{i,j}~ đồng. Hãy tìm hành trình có chi phí nhỏ nhất, đi qua mỗi thành phố đúng một lần rồi quay trở về thành phố xuất phát.

Lưu ý rằng chi phí không nhất thiết đối xứng: ~A_{i,j}~ có thể khác ~A_{j,i}~.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên ~n~.
• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa ~n~ số nguyên ~A_{i,1}, A_{i,2}, \ldots, A_{i,n}~.

Kết quả

In ra một số nguyên là chi phí nhỏ nhất.

Ví dụ

Đầu vào:

5
0 2 8 5 1
10 0 5 9 9
3 5 0 6 6
2 8 2 0 2
6 3 8 7 0

Đầu ra:

17

Giải thích: Hành trình ~1 \to 5 \to 2 \to 3 \to 4 \to 1~ có chi phí ~1 + 3 + 5 + 6 + 2 = 17~, và đó là chi phí nhỏ nhất.

Giới hạn

• ~1 \le n \le 10~
• ~1 \le A_{i,j} \le 1000~ với ~i \ne j~
• ~A_{i,i} = 0~

Với ~n = 1~, hành trình không cần đi đâu cả nên chi phí là ~0~.