녹색 옷 입은 애가 모험가지?

N×N 격자에서 (0,0)부터 (N-1,N-1)까지 이동하는 최소 비용 경로를 구한다. 각 칸에 이동 비용이 있으며, 이동은 상하좌우 4방향이다. 방문한 칸을 다시 방문할 수 있다.

다익스트라 알고리즘으로 풀 수 있다. 시작 칸의 비용도 합산한다.

입력

첫째 줄에 N이 주어진다.

다음 N개 줄에 각 칸의 비용이 공백으로 구분되어 주어진다.

• 2 ≤ N ≤ 125
• 1 ≤ 비용 ≤ 100

출력

최소 비용을 출력한다.

예제 입력 1

4
1 2 3 1
1 3 1 1
1 1 1 5
1 2 2 1

예제 출력 1

9