Cho một hình vuông A gồm n×n ô vuông, trên mỗi ô vuông chứa 1 số nguyên(n≤1000), các dòng được đánh số trên xuống dưới bắt đầu từ 1, các cột được đánh số từ trái qua phải cũng bắt đầu từ 1. Mỗi số trong bảng có giá trị tuyệt đối không vượt quá 10000. Đường chéo chính của bảng là đường thẳng nối hai ô (1,1) và(n,n).

Yêu cầu: Hãy tìm phần tử lớn nhất thuộc các ô nằm trên đường chéo chính.

Dữ liệu vào:

• Dòng đầu chứa số n.
• Dòng thứ i trong n dòng tiếp theo chứa n số nguyên lần lượt ứng với các phần tử nằm trên dòng thứ i của bảng A.

Dữ liệu ra:

• Ghi một số nguyên duy nhất là kết quả bài toán trên.

Ví dụ:

Input

4
1 2 3 4
4 3 2 0
0 2 3 4
1 4 5 6

Output

6