Khu rừng có dạng một bảng $n\times n$. Ở mỗi ô $(i,j)$ Marisa có thể đến ô $(i+1,j)$ hoặc $(i,j+1)$.

Ô $(i,j)$ có $A_{i,j}$ cây nấm. Hành trình của Marisa bắt đầu từ $(1,1)$ và kết thúc ở $(n,n)$. Hỏi Marisa có thể hái được nhiều nhất bao nhiêu cây nấm?

Input

• $n$ dòng, mỗi dòng gồm $n$ số nguyên.

Output

• Một số nguyên duy nhất số cây nấm lớn nhất Marisa có thể hái.

Điều kiện

• $1\le A\le {10}^3$
• $1\le A_{i,j}\le {10}^9$

Sample Input 1

4
2 2 2 1
1 1 2 1
1 1 2 1
1 1 2 2

Sample Output 1

14