Với các bé ngoài việc học tập thì chúng cũng rất cần được thoả mãn nhu cầu vui chơi, giải trí. Trò “Chơi bi” vừa giúp bé có những giây phút thư giãn bên bạn bè vừa rèn luyện khả năng khéo léo khi phải cố gắng để bắn trúng những mục tiêu khác nhau.

Chơi bi hứa hẹn sẽ giúp các bé gắn kết hơn với thiên nhiên, cây cối, bớt ham mê những trò chơi điện tử vô bổ (trừ LOL). Thế giới của các bé sẽ rộng mở hơn, cùng bạn bè tạo nên những kỷ niệm giản dị nhưng thật quý báu, làm giàu thêm tình cảm, trí tuệ.

Nguồn: https://specialkid.vn/

Một hôm, đang trên đường ra sân để học thể dục, Phọm thấy rất nhiều bi vương vãi trên sân, là một “nhà sưu tầm bi”, cậu không thể bỏ lỡ cơ hội làm giàu hiếm có này. Tuy nhiên, cũng sắp trễ giờ học rồi nên cậu không thể nhặt hết bi mà chỉ nhặt bi từ phía cậu đang chạy về phía sân học thể dục.

Bãi bi có dạng một hình vuông kích thước $n\ast n$, Phọm xuất phát tại ô $(1,1)$ và kết thúc tại ô $(n,n)$ cũng là vị trí cuối cùng mà cậu sẽ nhặt trước khi đến sân thể dục đúng giờ. Mỗi lần di chuyển từ ô $(x,y)$ cậu chỉ có thể đi tới ô $(x+1,y)$ hoặc $(x,y+1)$ để nhặt bi. Do Phọm không còn thời gian để suy nghĩ nên bạn hãy giúp cậu nhóc tìm đường đi sao cho số bi cậu kiếm được là lớn nhất.

Input

Dòng đầu tiên chứa một số nguyên $n$ ($1\le n\le 5000$).

$n$ dòng tiếp theo, dòng thứ $i$ chứa $n$ số nguyên, số nguyên thứ $j$ là $a_{ij}$ ($0\le a_{ij}\le 10000$) thể hiện số viên bi ở trên ô $(i,j)$.

Output

Gồm một số nguyên duy nhất là số bi tối đa Phọm có thể lụm được.

Sample Input

4
3 3 3 4
2 3 2 2
3 4 5 6
2 3 8 8

Sample Output

34

Subtasks

Subtask 1(40%): $n\le 15$.

Subtask 2(60%): Không có ràng buộc gì thêm.