Minimum Toll

Problem Description

A merchant crosses an $N\times N$ square grid to attend an important business event. He enters at the top-left corner and exits at the bottom-right corner. Crossing each small cell takes 1 unit of time. The merchant must exit within $2N-1$ units of time. While passing through each intermediate cell, a toll must be paid.

The merchant wants to cross with the minimum total toll within the required time. What is the minimum toll required?

Note: diagonal moves are not allowed (you may only move up, down, left, or right, and may not leave the grid).

Input Format

The first line is an integer — the grid width $N\ (1\le N<100)$.

The following $N$ lines each contain $N$ integers not greater than $100$ — the toll of each cell.

Output Format

The minimum toll required.

Sample Input

5
1  4  6  8  10 
2  5  7  15 17 
6  8  9  18 20 
10 11 12 19 21 
20 23 25 29 33

Sample Output

109

Hint

In the sample, the minimum is $109=1+2+5+7+9+12+19+21+33$.

Source: ybt (一本通 online judge).