가장 짧은 항해 시간

검의 해안 바다는 $n \times n$개의 구역으로 나뉜다($1 \le n \le 50$). 구역마다 바다의 상태가 다르다. 배는 지금 있는 구역에서 북쪽, 남쪽, 동쪽, 서쪽으로 이웃한 구역으로만 움직이고, 격자 밖으로는 나가지 못한다. 한 구역에서 이웃 구역으로 옮겨 가는 데 걸리는 시간은 도착하는 구역만으로 정해지며, 그 값은 1000 이하의 양의 정수다. 예를 들어 $t[4,4] = 10$이면 $(3,4)$, $(5,4)$, $(4,5)$, $(4,3)$ 가운데 어디에서 출발하든 $(4,4)$에 닿기까지 10시간이 걸린다.

바다에서 방향을 바꾸는 일은 쉽지 않다. 선원은 바뀐 바람에 다시 맞춰야 하고, 배는 속도를 줄였다가 다시 올려야 한다. 이미 한 방향으로 나아가던 배가 진로를 바꾸면 정확히 3시간이 더 걸린다. 예를 들어 $t[4,4] = 10$이고 $t[4,5] = 20$이면 $(4,3)$, $(4,4)$, $(4,5)$ 순서로 항해할 때는 30시간이 걸리지만, $(3,4)$, $(4,4)$, $(4,5)$ 순서로 항해할 때는 3시간이 더 붙어 33시간이 걸린다.

배는 $(1,1)$에서 멈춘 상태로 출발하므로 첫 이동에는 방향 전환 시간이 붙지 않는다. 한 구역을 여러 번 지나가도 되고, 지나갈 때마다 그 구역의 시간을 다시 낸다.

마법사 엘민스터는 지금 $(1,1)$ 구역에 있고, $(n,n)$ 구역에 있는 발더스 게이트로 되도록 빨리 가려고 한다. 방향 전환 시간을 모두 더해서 가장 짧은 시간을 구하시오.

첫째 줄에 정수 $n$이 주어진다. 이어지는 $n$개 줄에 시간 배열이 주어진다. 둘째 줄에는 $t[1,1]$, $t[1,2]$, $\cdots$, $t[1,n]$이, 셋째 줄에는 $t[2,1]$, $t[2,2]$, $\cdots$, $t[2,n]$이 주어지고, 같은 방식으로 이어져 마지막 $(n+1)$번째 줄에는 $t[n,1]$, $t[n,2]$, $\cdots$, $t[n,n]$이 주어진다. $t[1,1]$은 항상 0이다.

엘민스터가 발더스 게이트에 닿는 데 걸리는 가장 짧은 시간을 정수 하나로 출력한다.