Bajirao's city has N X N police stations P(i,j) (1 ≤ i ≤ N, 1 ≤ j ≤ N) arranged in an N X N square matrix format. Bajirao is a really hardworking police officer and wants to solve all the pending cases of all the police stations in his city. However, the Police Commissioner (his senior) is not allowing him to do so due to political pressure. Bajirao is too passionate about solving cases and hence the Police Commissioner has decided to transfer him to another city after N days (Day 1, Day 2 .... Day N).
Each police station P(i,j) has a single dedicated vehicle V(i,j) to aid Bajirao's transport.
Every vehicle V(i,j) belonging to police station P(i,j) can drop Bajirao to either police station P(i,2j) (if 2j ≤ N) or police station P(i,j/2) (if j/2 ≥ 1) (Integer division, For eg. 4/2=2 and 7/2=3). Once vehicle V(i,j) drops Bajirao, it returns to Police Station P(i,j).
On the i th day, he can solve all the pending cases of exactly 1 police station present in the i th row.
On the 1st day, Bajirao can visit any Police Station of his choice, choose one of them and solve all its pending cases.
Say on the (i-1)th day (i ≥ 2) Bajirao solves all the pending cases of police station P(i-1,x). Vehicle V(i-1,x) takes him home, drops him to P(i,x) the next day and returns to Police Station P(i-1,x).

Bajirao wants to solve as many cases as possible before he gets transferred to another city. What is the maximum number of cases he can solve?

Input :

First line consists of N. The next N lines are such that each line consists of N space separated integers such that the j th integer on the i th line represents the number of pending cases in Police Station P(i,j).

Output :

A single integer denoting the answer to the given problem.

Constraints :

1 ≤ N ≤ 100

1 ≤ Number of pending cases in P(i,j) ≤ 1000

Author : Shreyans

Tester : Sayan

(By IIT Kgp HackerEarth Programming Club)

SAMPLE INPUT
3
1 2 3
3 1 2
1 4 1

SAMPLE OUTPUT
10

Explanation

On the first day, Bajirao solves all the 3 cases of P(1,3). V(1,3) takes him home.

On the second day, V(1,3) drops him to P(2,3). V(2,3) drops him to P(2,3/2) ie. P(2,1). Bajirao solves all the 3 cases of P(2,1). V(2,1) takes him home.

On the third day, V(2,1) drops him to P(3,1). V(3,1) drops him to V(3,2*1) ie. P(3,2). Bajirao solves all the 4 cases of P(3,2). V(3,2) takes him home.

Bajirao's stay in his city is over. He was able to solve 3 + 3 + 4 = 10 cases.

见题面

见题面