Array Escape

Sangsu owns a two dimensional array $A[1..n][1..n]$ of size $n \times n$. Here $n$ is a natural number that is at least 2, and every element of the array is an integer between 1 and 222.

Seunghyeon saw Sangsu playing with the array, burned with envy, and locked Sangsu inside $A[1][1]$. Seunghyeon still had a little conscience left, so he built an exit at $A[n][n]$ and told Sangsu about it.

[Figure 1] When $n = 4$, Sangsu stands on $A[1][1]$ and the exit is at $A[4][4]$.

Sangsu wants to reach the exit at $A[n][n]$ as fast as possible. Suppose Sangsu stands on $A[i][j]$. To follow a shortest route, he moves under the conditions below.

1. If $1 \le i, j < n$, he jumps only to $A[i][j+1]$ or to $A[i+1][j]$.
2. If $i = n$ and $1 \le j < n$, he jumps only to $A[i][j+1]$.
3. If $1 \le i < n$ and $j = n$, he jumps only to $A[i+1][j]$.
4. If $i = j = n$, he walks straight out through the exit.

[Figure 2] Suppose $n = 5$. The arrow marked (ㄱ) satisfies condition 1, the arrow marked (ㄴ) satisfies condition 2, and the arrow marked (ㄷ) satisfies condition 3.

A jump carries one more restriction. For Sangsu to jump from $A[a][b]$ to $A[c][d]$, the values must satisfy $A[a][b] > A[c][d]$. Sangsu felt that no route could keep this condition. Luckily, before Seunghyeon locked him in, Sangsu had built a button on every element of the array, and pressing a button raises that element by 1. (Sangsu can press only the button of the element he stands on.) Thanks to those buttons, Sangsu can always escape the array.

[Figure 3] Suppose $n = 2$. Since $A[1][1] = 5 > A[1][2] = 2$, Sangsu can jump from $A[1][1]$ to $A[1][2]$. To jump from $A[1][1]$ to $A[2][1]$ instead, he presses the button on $A[1][1]$ twice so that $A[1][1]$ becomes 7.

Each button press costs 1 won. Sangsu wants to escape the array while spending as little money as possible. Help Sangsu.

The first line contains $n$. ($2 \le n \le 2{,}222$)

The next $n$ lines follow. The $i$-th of them ($1 \le i \le n$) contains the $n$ numbers $A[i][1], A[i][2], \dots, A[i][n-1], A[i][n]$ in order, separated by spaces.

Print the minimum cost in won that Sangsu has to spend to escape the array.

In the first example, Sangsu can escape along the route drawn below.

This route spends 2 won on $A[1][1]$ and 1 won on $A[3][2]$, for a total of 3 won, and that total is the minimum.