Có \(n\) người và \(n\) công việc. Người thứ \(i\) làm công việc \(j\) hết \(C[i][j]\) đơn vị thời gian. Nhiệm vụ của bạn là phân chia cho mỗi người một công việc sao cho thời gian hoàn thành tất cả các công việc là sớm nhất.

Input

• Dòng đầu là số \(n\) tượng trưng cho số công việc và số người (\( 1 <= n <= 500 \))
• \(n\) dòng tiếp theo mỗi dòng có \(n\) số, dòng i cột j tượng trưng cho \(C[i][j]\) (\(1 <= C[i][j] <= 100000 \))

Output

• Số nguyên duy nhất chỉ thời gian hoàn thành sớm nhất

Example

Input:

4
10 10 10 2
10 10 3 10
4 10 10 10
10 5 10 10

5