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