Maximum path sum 3

Cho mảng 2 chiều A gồm N hàng và N cột, hàng được đánh số từ 1 đến N từ trên xuống dưới, cột cũng được đánh số từ 1 tới N từ trái sang phải, hãy tìm 1 đường đi từ một ô ở cột 1 tới 1 ổ ở cột N sao cho các phần tử trên đường đi đó là lớn nhất có thể. Biết rằng ở mỗi bước đi từ ô hiện tại (i, j) chỉ có thể đi sang phải (i, j + 1) hoặc đi xuống ô dưới bên phải (i + 1, j + 1), ô bên trên bên phải(i - 1, j + 1). Hãy tìm 1 đường đi có tổng các số trên đường đi là lớn nhất.

Input Format

Dòng đầu tiên là 1 số nguyên N. N dòng tiếp theo mỗi dòng gồm N số. (1<=N<=100;-100<=A[i][j]<=100)

Constraints

.

Output Format

In ra đáp án của bài toán.

Ví dụ:

Dữ liệu vào

5
2 -8 2 9 0 
-5 6 6 -1 6 
3 5 0 2 9 
9 -8 9 7 0 
-4 6 1 -2 0

Dữ liệu ra

40