배열 탈출

상수에게는 크기가 $n \times n$인 2차원 배열 $A[1..n][1..n]$이 있습니다. $n$은 2 이상의 자연수이고, 배열의 각 원소는 1 이상 222 이하의 정수입니다.

배열을 가지고 놀던 상수를 본 승현이는 질투심이 불타올라 상수를 $A[1][1]$에 가둬 버렸습니다! 그래도 최소한의 양심은 있었는지, 승현이는 $A[n][n]$에 출구를 만들어 놓고 그 사실을 상수에게 알려 줬습니다.

[그림 1] $n = 4$라면 상수는 $A[1][1]$에 있고, 출구는 $A[4][4]$에 있습니다.

상수는 가능한 한 빨리 출구인 $A[n][n]$에 도달하려 합니다. 상수가 $A[i][j]$에 있다고 할 때, 최단 경로로 이동하려면 다음 조건을 지켜야 합니다.

1. $1 \le i, j < n$이라면 $A[i][j+1]$ 또는 $A[i+1][j]$로만 건너뜁니다.
2. $i = n$이고 $1 \le j < n$이라면 $A[i][j+1]$로만 건너뜁니다.
3. $1 \le i < n$이고 $j = n$이라면 $A[i+1][j]$로만 건너뜁니다.
4. $i = j = n$이라면 바로 출구로 나갑니다.

[그림 2] $n = 5$라고 합시다. (ㄱ)은 1번 조건을 만족하고, (ㄴ)은 2번 조건을 만족하며, (ㄷ)은 3번 조건을 만족합니다.

건너뛸 때에도 제약이 따릅니다. 상수가 $A[a][b]$에서 $A[c][d]$로 건너가려면 $A[a][b] > A[c][d]$를 만족해야 합니다. 상수는 왜인지 이 조건을 만족하면서 이동할 수 없을 것 같았습니다. 다행히도 승현이가 상수를 배열에 가둬 버리기 전에, 상수는 배열의 각 원소에 버튼을 만들어 놓아서, 이 버튼을 누르면 그 원소의 값이 1 증가하도록 했습니다. (물론 상수는 자신이 서 있는 원소의 버튼만 누를 수 있습니다.) 이 버튼 덕분에 상수는 항상 배열을 탈출할 수 있습니다!

[그림 3] $n = 2$라고 합시다. $A[1][1] = 5 > A[1][2] = 2$이므로, 상수는 $A[1][1]$에서 $A[1][2]$로 건너갈 수 있습니다. 상수가 $A[1][1]$에서 $A[2][1]$로 건너가려면, $A[1][1]$에 있는 버튼을 두 번 눌러 $A[1][1]$의 값을 7로 만들면 됩니다.

하지만 버튼을 한 번 누르는 데에는 1원의 비용이 듭니다. 상수는 돈을 가능한 한 적게 들이면서 배열을 탈출하려 합니다. 상수를 도와주세요.

첫 번째 줄에 $n$이 주어집니다. ($2 \le n \le 2{,}222$)

다음 $n$개 줄이 주어집니다. 이 중 $i$($1 \le i \le n$)번째 줄에는 $n$개의 수 $A[i][1], A[i][2], \dots, A[i][n-1], A[i][n]$이 공백을 사이에 두고 차례대로 주어집니다.

첫 번째 줄에 상수가 배열을 탈출하기 위해 들여야 할 최소 비용을 원 단위로 출력합니다.

첫 번째 예제에서 상수는 아래 그림과 같은 방법으로 탈출할 수 있습니다.

이렇게 하면 $A[1][1]$에서 2원, $A[3][2]$에서 1원의 비용이 들어 총 3원의 비용이 들게 되며, 이것이 최소입니다.