Now after having the event list, all the participants wanted to know where to go for their respective events, for this purpose they are given a piece of paper with an n x n grid of numbers printed on it. They are told that their event would be held in a room denoted by the number which they get on finding the minimum possible path sum for reaching from the leftmost column of the grid to the rightmost column of the grid. All the participants are confused and look to you for your help. Help them find their way across the Grid so that they can participate in their events.

Input:

First line contains n, then n lines follow consisting of n elements each.

Output:

Output is a single integer denoting the minimum possible path sum.

Constraints:

1 ≤ n ≤ 1000

1 ≤ (values in matrix) ≤ 1000

SAMPLE INPUT
5
131	673	234	103	16
199	96	342	965	150
630	803	746	422	111
537	699	497	121	956
805	732	524	37	331

SAMPLE OUTPUT
990

Explanation

199 -> 96 ->342 -> 234 -> 103 -> 16

This is the path with the minimum possible path sum in the sample grid reaching from the leftmost column to the rightmost column.
N=input();
matrix = [map(int,raw_input().strip().split()) for x in xrange(N)]
n, m = len(matrix), len(matrix[0]) 
cost = [matrix[i][-1] for i in xrange(n)]

for i in xrange(m-2, -1, -1):
	cost[0] += matrix[0][i]
	for j in xrange(1, n):
		cost[j] = min(cost[j], cost[j-1]) + matrix[j][i]
	for j in xrange(n-2, -1, -1):
		cost[j] = min(cost[j], cost[j+1] + matrix[j][i])

print min(cost)