Array Escape

Interview

Time limit2sMemory limit256 MB

Summary

Find the cheapest right-and-down path through a square grid where stepping to a higher or equal neighbor costs the raises needed to exceed it.

Level: Easy3 of 10
Topics: Dynamic programming, Shortest path, Matrix
Solved: No attempts yet

Problem

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.

If $1 \le i, j < n$ , he jumps only to $A[i][j+1]$ or to $A[i+1][j]$ .
If $i = n$ and $1 \le j < n$ , he jumps only to $A[i][j+1]$ .
If $1 \le i < n$ and $j = n$ , he jumps only to $A[i+1][j]$ .
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.

Input

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.

Output

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

Hint

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.

Examples7

Example 1
Input
```
4
5 2 4 3
6 5 1 2
3 4 5 3
7 4 3 1
```
Expected output
```
3
```

Example 2

Input

Expected output

Example 3
Input
```
2
222 2
3 1
```
Expected output
```
0
```
Example 4
Input
```
2
1 222
222 222
```
Expected output
```
223
```

Example 5

Input

3
222 222 222
222 222 222
222 222 222

Expected output

Example 6
Input
```
3
1 2 3
4 5 6
7 8 9
```
Expected output
```
12
```

Example 7

Input

4
10 9 8 7
200 200 200 6
200 200 200 5
200 200 200 4

Expected output