Tèo là đội trưởng đội công nhân vận chuyển trong một nhà máy chế biến thủy sản ở vùng duyên hải. Hôm nay ban giám đốc yêu cầu \(N\) công nhân phải hoàn thành \(N\) công việc khác nhau, mỗi công nhân chỉ làm đúng một công việc và mỗi công việc chỉ giao cho đúng một công nhân. Biết rằng nếu công nhân \(i\) làm công việc \(j\) sẽ mất \(c_{i,j}\) phút, Tèo cần phân công sao cho tổng thời gian hoàn thành của cả nhóm là nhỏ nhất để kịp chuyến xe giao hàng chiều nay.

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

• Dòng đầu chứa số nguyên dương \(N\) (\(1 \le N \le 15\)).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa \(N\) số nguyên \(c_{i,0}, c_{i,1}, \ldots, c_{i,N-1}\) (\(1 \le c_{i,j} \le 10^3\)).

Định dạng đầu ra

• In ra một số nguyên duy nhất là tổng thời gian nhỏ nhất khi phân công hợp lý.

Ví dụ

Input:

3
9 2 7
6 4 3
5 7 1

Output:

10

Giải thích: Phân công: công nhân \(0\) làm việc \(1\) (\(2\) phút), công nhân \(1\) làm việc \(2\) (\(3\) phút), công nhân \(2\) làm việc \(0\) (\(5\) phút). Tổng: \(2+3+5 = 10\).

Ràng buộc

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