Cho một bảng ~A~ gồm ~n×n~ 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)~. Như vậy trên bảng có ~2n-1~ đuờng chéo song song với đường chéo chính.

Yêu cầu: Hãy tìm đường chéo song song với đường chéo chính có tổng các phần tử trên đường chéo đó là lớn nhất.

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~.

Kết quả:

• Ghi một số nguyên duy nhất là tổng các phần tử trên đường chéo mà bạn tìm được.

Ví dụ:

Input

4 
1 2 4 3
3 4 2 5
2 5 4 3
4 3 2 5 

Output

14