Bharat is chocoholic. He found a chocolate factory of N floors ,but the factory has N*N rooms where in each room specific number of chocolate is present. Now, Bharat starts collecting chocolate from ground floor. He can only collect chocolate from one room in a floor. Bharat can only move to upper room or upper-right room or upper-left room .

He want to collect maximum number of chocolate possible. Help him in finding maximum number of chocolate.

Input:

First line contains a value of N. Next N lines contains N space separated integer.

Output:

Output a single integer denoting the maximum number of chocolate Bharat can collect.

Constraints

1 <= N <= 1000

1 <= Number chocolate in 1 room <= 10^5