Maximum path sum 2.

Cho mảng 2 chiều A gồm N hàng và N cột, hãy tìm 1 đường đi từ dòng A[1][1] tới dòng A[N][i] 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 chỉ có thể đi xuống ô dưới bên trái, ô dưới bên phải hoặc ô dưới của ô hiện tại. 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;1<=A[i][j]<=100)

Constraints

.

Output Format

In ra kết quả của bài toán.

Ví dụ:

Dữ liệu vào

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

Dữ liệu ra

33