Một nhân viên giao hàng của công ty chuyển phát nhanh cần giao hàng cho \(N\) điểm trong thành phố, được đánh số từ \(0\) đến \(N - 1\). Anh xuất phát từ điểm \(0\) (kho hàng) và phải kết thúc hành trình tại điểm \(N - 1\) (điểm cuối). Biết chi phí xăng để đi từ điểm \(i\) đến điểm \(j\) là \(c_{i,j}\) đồng. Yêu cầu của công ty là mỗi điểm (trừ điểm xuất phát \(0\) và điểm kết thúc \(N-1\)) chỉ được ghé qua đúng một lần trong hành trình.

Hãy tìm tổng chi phí nhỏ nhất để anh nhân viên đi từ \(0\) đến \(N-1\) và ghé qua tất cả các điểm còn lại đúng một lần.

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

• Dòng đầu tiên chứa số nguyên \(N\) (\(2 \le N \le 20\)).
• \(N\) dòng tiếp theo, mỗi dòng chứa \(N\) số nguyên \(c_{i,j}\) (\(1 \le c_{i,j} \le 10^6\)). Đường chéo chính có giá trị \(0\).

Định dạng đầu ra

• In ra tổng chi phí nhỏ nhất.

Ví dụ

Input:

4
0 10 15 20
10 0 35 25
15 35 0 30
20 25 30 0

Output:

75

Ràng buộc

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