Phân công công việc

Một công ty có \(n\) công nhân và \(n\) công việc cần được thực hiện. Chi phí để công nhân thứ \(i\) thực hiện công việc thứ \(j\) được cho bởi ma trận \(a[i][j]\) (\(1 \le i, j \le n\)). Mỗi công nhân phải được giao đúng một công việc, và mỗi công việc phải được giao cho đúng một công nhân.

Yêu cầu: Hãy phân công \(n\) công việc cho \(n\) công nhân sao cho tổng chi phí phải trả là nhỏ nhất.

Input

Dữ liệu vào:

• Dòng 1: số nguyên \(n\) (\(2 \le n \le 100\)) là số công nhân và số công việc.

• Dòng 2 đến \(n+1\): mỗi dòng gồm \(n\) số nguyên \(a[i][j]\) (\(1 \le a[i][j] \le 10^5\)), là chi phí để công nhân \(i\) làm công việc \(j\).

Ràng buộc:

• Có \(60\%\) số test của bài thỏa mãn \(2 \le n \le 20\), \(1 \le a[i][j] \le 10^3\).

• Có \(40\%\) số test của bài thỏa mãn \(20 < n \le 100\), \(1 \le a[i][j] \le 10^5\).

Output

In ra một số nguyên là tổng chi phí nhỏ nhất phải trả khi phân công công việc tối ưu.

Example

Input:

4
100 20 50 60
30 20 10 60
40 50 10 20
10 50 70 80

Output:

60

Note

Công nhân \(1, 2, 3\) và \(4\) lần lượt thực hiện các công việc \(2, 3, 4, 1\) tương ứng. Tổng chi phí \(= 20 + 10 + 20 + 10 = 60\).