Sau khi giải cứu vũ trụ thành công, Prototype và uou đứng trước những cánh cổng không gian chuẩn bị chia tay để trở về thế giới riêng của mình. Tuy nhiên, hệ thống điều khiển cổng đang gặp sự cố. Có \(n\) siêu anh hùng và \(n\) cổng không gian. Để kích hoạt hệ thống dịch chuyển, mỗi siêu anh hùng phải đứng vào một cổng. Prototype nhận ra rằng mỗi siêu anh hùng \(i\) khi đứng vào cổng \(j\) sẽ tiêu tốn một lượng năng lượng là \(C_{i,j}\). Nhưng trớ trêu thay, hệ thống chỉ hoạt động nếu tổng năng lượng tiêu tốn là nhỏ nhất (để dành năng lượng mở cổng ổn định). uou thách thức Prototype: "Nếu cậu tìm được cách phân công tối ưu và tính được tổng năng lượng nhỏ nhất đó, chúng ta sẽ gặp lại nhau ở vũ trụ số 0!". Prototype đang bối rối vì lần này số lượng siêu anh hùng lên tới hàng trăm người. Bạn hãy giúp Prototype giữ trọn lời hứa với uou.

Yêu cầu: Cho ma trận chi phí \(C\) kích thước \(n \times n\). Hãy tìm cách phân công mỗi siêu anh hùng vào đúng một cổng sao cho tổng chi phí là nhỏ nhất.

Input

• Dòng đầu tiên chứa số nguyên \(n\) (\(1 \le n \le 200\)).
• \(n\) dòng tiếp theo, mỗi dòng chứa \(n\) số nguyên. Số thứ \(j\) ở dòng thứ \(i\) là \(C_{i,j}\) (\(0 \le C_{i,j} \le 10^6\)).

Output

• Một số nguyên duy nhất đại diện cho tổng năng lượng tiêu tốn nhỏ nhất tìm được.

Example

3
10 15 20
5 30 10
10 10 10

25

Scoring

• Subtask 1 (\(10\%\) điểm): \(n \le 8\)
• Subtask 2 (\(20\%\) điểm): \(n \le 20\)
• Subtask 3 (\(30\%\) điểm): \(n \le 100\) và \(A_{i,j} \le 1000\)
• Subtask 4: Không có ràng buộc gì thêm