Description

A merchant is traversing through an N×N grid to attend a very important business event. He must enter from the top-left corner and exit from the bottom-right corner. Crossing each small square in the grid takes 1 unit of time. The merchant must exit within (2N-1) units of time. While passing through each small square, a certain fee must be paid.

The merchant aims to cross the grid with the minimum cost within the given time limit. What is the minimum cost required? Note: Diagonal movement through the squares is not allowed (i.e., movement is restricted to up, down, left, and right directions, and the merchant cannot leave the grid).

Input Format

The first line is an integer representing the width N of the square grid (1 ≤ N < 100).
The following N lines each contain N integers (each no greater than 100), representing the fees for each small square in the grid.

Output Format

The minimum cost required.

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

109

Hint

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