Một dây chuyền sản xuất có ~N~ vị trí làm việc đánh số từ ~1~ đến ~N~. Có ~N~ công nhân để xếp vào làm việc trên các vị trí này. Biết ~s_{ij}~ là năng suất làm việc của công nhân ~i~ trên vị trí làm việc ~j~ của dây chuyền ~(i, j = 1,2,..,N)~. Cho trước một cách bố trí công nhân đứng làm việc trên các vị trí của dây chuyền, năng suất của dây chuyền theo cách bố trí đã cho sẽ là năng suất của công nhân có năng suất thấp nhất trong số tất cả các công nhân trên dây chuyền.

Yêu cầu: Tìm cách bố trí ~N~ công nhân vào làm việc trên ~N~ vị trí của một dây chuyền sản xuất sao cho năng suất của dây chuyền là lớn nhất và một công nhân chỉ làm đúng một công việc, một công việc chỉ được làm bởi đúng một công nhân.

Dữ liệu vào

• Dòng đầu tiên ghi số nguyên dương ~N~ ~(N ≤ 1000)~;
• Dòng thứ ~i~ trong số ~N~ dòng tiếp theo ghi ~N~ số nguyên dương ~s_{i1} , s_{i2}, ..., s_{iN}~ , hai số liên tiếp được ghi cách nhau bởi dấu cách, ~i = 1, 2, ...,N~ ~(s_{ij} ≤ 10^9)~.

Kết quả

Năng suất của dây chuyền theo cách bố trí tìm được

Ví dụ

Input

4
9 4 4 12
8 7 8 13
2 2 8 3
6 7 3 7

Output

7

Giải thích

Trong ví dụ trên ta sẽ sắp xếp để công nhân ~1~ làm việc ~1~ với năng suất là ~9~, công nhân ~2~ làm việc ~2~ với năng suất là ~7~, công nhân ~3~ làm việc ~3~ với năng suất là ~8~ và cuối cùng công nhân ~4~ làm việc ~4~ với năng suất là ~7~, do đó năng suất của dây chuyền sản xuất sẽ là ~7~.