Công ty của ông Giám đốc Hùng vừa nhận đúng \(N\) dự án khác nhau và cũng có đúng \(N\) nhân viên đang rảnh việc. Mỗi nhân viên chỉ có thể đảm nhận một dự án và mỗi dự án chỉ cần đúng một người phụ trách. Nếu giao nhân viên thứ \(i\) làm dự án thứ \(j\) thì thời gian hoàn thành dự án đó là \(c_{i,j}\) ngày. Ông Hùng muốn phân công sao cho tổng thời gian hoàn thành toàn bộ \(N\) dự án là ngắn nhất, vì mỗi ngày chờ đều tốn thêm chi phí quản lý.

Hãy giúp ông Hùng tìm cách phân công tối ưu và cho biết tổng thời gian nhỏ nhất.

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

• Dòng đầu tiên chứa số nguyên \(N\) (\(1 \le N \le 20\)).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa \(N\) số nguyên \(c_{i,1}, c_{i,2}, \dots, c_{i,N}\) (\(1 \le c_{i,j} \le 100\)).

Định dạng đầu ra

• In ra tổng thời gian nhỏ nhất để hoàn thành tất cả dự án.

Ví dụ

Input:

3
3 2 7
5 1 3
2 6 4

Output:

6

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.