Sau khi tìm được kho báu, Anny sắp xếp một chuyến đi du lịch vòng quanh thế giới. Có ~N~ điểm du lịch Anny muốn ghé thăm, được đánh số từ ~1~ đến ~N~. Giữa các điểm du lịch có các chuyến bay đi trực tiếp; chi phí để bay từ điểm ~i~ đến điểm ~j~ là ~C_{ij}~ (có thể khác ~C_{ji}~) và ~1 \le C_{ij} \le 10^9~.

Anny muốn chọn một hành trình du lịch qua ~N~ điểm, mỗi điểm chỉ ghé thăm một lần duy nhất. Với tinh thần tiết kiệm, Anny muốn chọn một hành trình du lịch với tổng chi phí nhỏ nhất.

Yêu cầu: Hãy giúp Anny tìm được hành trình có tổng chi phí nhỏ nhất.

Input

Vào từ tập tin DULICH.INP, có cấu trúc như sau:

• Dòng đầu ghi số nguyên dương ~N~;
• Dòng thứ ~i~ trong ~N~ dòng tiếp theo, ghi ~N~ số nguyên không âm ~C_{ij}~ là chi phí bay từ điểm ~i~ đến điểm ~j~ ~(1 \le j \le N)~.

Output

Ghi vào tập tin DULICH.OUT, gồm một số nguyên dương duy nhất là tổng chi phí của hành trình nhỏ nhất tìm được.

Ví dụ

Input

6
0 1 2 1 3 4
5 0 3 2 3 4
4 1 0 2 1 2
4 2 5 0 4 3
2 5 3 5 0 2
5 4 3 3 1 0

Output

8

Giải thích

Một hành trình có tổng chi phí nhỏ nhất là ~6 \to 5 \to 1 \to 3 \to 2 \to 4~ với tổng chi phí ~1 + 2 + 2 + 1 + 2 = 8~ (hành trình có thể bắt đầu tại một điểm bất kỳ và không cần quay lại điểm xuất phát).

Giới hạn

• ~1 \le C_{ij} \le 10^9~ với ~i \ne j~.
• Có 50% số test ứng với 50% số điểm có: ~5 < N \le 10~;
• Có 50% số test ứng với 50% số điểm có: ~10 < N \le 15~.