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.