Minimum toll

Title Description

A businessman walked through a $N\times N$ A grid of squares , Go to a very important business activity .

He wants to enter from the upper left corner of the grid , Lower right corner out .

Every time you cross the middle 1 A small square , All costs. 1 Unit time .

Businessmen must be in $(2N-1)$ A unit of time goes through .

And when passing through each small square in the middle , All need to pay a certain fee .

The merchant expects to cross out with the least cost within the specified time .

How much does it cost at least ？

Be careful ： You can't cross small squares diagonally （ namely , It can only move up, down, left and right, and cannot leave the grid ）.

Input format

The first line is an integer , Represents the width of the square $N$.

Back $N$ That's ok , Each row $N$ No more than one. 100 The positive integer , For the cost of each small square on the grid .

Output format

Output an integer , Indicates the minimum cost required .

Data range

$1\le N\le 100$

Examples

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

Sample explanation

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

---

Ideas

This question is similar to the number triangle type , But it's a little different , Is to seek $mostSmallvalue$, Therefore, it is necessary to consider the initialization state and the judgment of out of bounds during state transition

---

C++ Code

#include <iostream>
#include <cstring>

using namespace std;

const int N = 110, INF = 1e9;

int a[N][N], f[N][N];
int n;

int main()
{
    scanf("%d", &n);

    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= n; j ++)
            scanf("%d", &a[i][j]);

    //  Initialize to positive infinity 
    memset(f,0x3f,sizeof f);            
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= n; j ++)
        {
            if (i == 1 && j == 1) f[i][j] = a[i][j];
            else f[i][j] = min(f[i - 1][j], f[i][j - 1]) + a[i][j]; 
        }

    printf("%d", f[n][n]);

    return 0;
}