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.
First line contains a value of N. Next N lines contains N space separated integer.
Output a single integer denoting the maximum number of chocolate Bharat can collect.
1 <= N <= 1000
1 <= Number chocolate in 1 room <= 10^5