Có \(N\) người và \(N\) công việc. Mỗi người có thể làm bất kỳ công việc nào, nhưng chi phí để người \(i\) làm công việc \(j\) là \(c_{ij}\). Mỗi người chỉ được làm đúng một công việc và mỗi công việc chỉ được giao cho đúng một người. Hãy tìm cách phân công sao cho tổng chi phí là nhỏ nhất.

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

• Dòng đầu chứa số nguyên \(N\) (\(1 \le N \le 500\)).
• \(N\) dòng tiếp theo, mỗi dòng chứa \(N\) số nguyên \(c_{ij}\) (\(1 \le c_{ij} \le 10^6\)).

Định dạng đầu ra

• Một số nguyên duy nhất là tổng chi phí nhỏ nhất.

Ràng buộc

Ví dụ

Input:

3
4 3 2
1 5 6
7 8 9

Output:

12