녹색 옷 입은 애가 젤다지?

시간 제한1초메모리 제한256 MB

요약

N x N 격자에서 각 칸을 지날 때 그 칸의 값을 비용으로 지불할 때, 왼쪽 위에서 오른쪽 아래까지 가는 최소 비용 경로를 구한다.

난이도: 보통10점 중 4점
유형: 그래프, 최단 경로, 행렬, 동적 계획법
정답자: 아직 제출이 없습니다

문제

젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 '도둑루피'라고 불리는 검은색 루피도 있는데, 이것을 얻으면 오히려 가지고 있던 루피가 줄어든다.

주인공 링크는 지금 도둑루피로만 가득 찬 $N \times N$ 크기 동굴의 가장 왼쪽 위 칸, 즉 $[0][0]$ 칸에 있다. 링크는 이 동굴의 반대편 출구인 가장 오른쪽 아래 칸 $[N-1][N-1]$ 까지 이동해야 한다.

동굴의 각 칸에는 도둑루피가 하나씩 놓여 있으며, 어떤 칸을 지나가면 그 칸에 적힌 도둑루피의 크기만큼 소지금을 잃는다. 이때 출발 칸과 도착 칸도 지나가는 칸에 포함된다. 링크는 한 번에 상하좌우로 인접한 칸으로 한 칸씩만 이동할 수 있다.

링크가 출발 칸에서 도착 칸까지 이동하면서 잃을 수밖에 없는 루피의 최소 합은 얼마인가?

입력

입력은 여러 개의 테스트 케이스로 이루어진다.

각 테스트 케이스의 첫째 줄에는 동굴의 크기를 나타내는 정수 $N$ 이 주어진다. ( $2 \le N \le 125$ )

이어지는 $N$ 개의 줄에는 각 줄마다 $N$ 개의 정수가 공백으로 구분되어 주어지며, 동굴의 각 칸에 놓인 도둑루피의 크기를 위쪽 줄부터 차례대로 나타낸다. 어떤 칸의 값이 $k$ 이면 그 칸을 지날 때 $k$ 루피를 잃는다는 뜻이다. 주어지는 모든 정수는 $0$ 이상 $9$ 이하의 한 자리 수다.

$N = 0$ 인 줄이 주어지면 전체 입력이 끝난다.

출력

각 테스트 케이스마다 한 줄에 답을 출력한다. $t$ 번째 테스트 케이스(번호는 $1$ 부터 시작한다)에 대해서는 Problem t: c 형식으로 출력하며, 여기서 $c$ 는 링크가 잃을 수밖에 없는 루피의 최소 합이다.

예제2

예제 1

입력

3
5 5 4
3 9 1
3 2 7
5
3 7 2 0 1
2 8 0 9 1
1 2 1 8 1
9 8 9 2 0
3 6 5 1 5
7
9 0 5 1 1 5 3
4 1 2 1 6 5 3
0 7 6 1 6 8 5
1 1 7 8 3 2 3
9 4 0 7 6 4 1
5 8 3 2 4 8 3
7 4 8 4 8 3 4
0

예상 출력

Problem 1: 20
Problem 2: 19
Problem 3: 36

예제 2
입력
```
2
1 2
3 4
0
```
예상 출력
```
Problem 1: 7
```