녹색 옷 입은 애가 젤다지?

https://www.acmicpc.net/problem/4485

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	19015	10017	6934	50.787%

문제

젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다.

그런데 간혹 ‘도둑루피’라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다!

젤다의 전설 시리즈의 주인공, 링크는 지금 도둑루피만 가득한 N x N 크기의 동굴의 제일 왼쪽 위에 있다.

[0][0]번 칸이기도 하다. 왜 이런 곳에 들어왔냐고 묻는다면

밖에서 사람들이 자꾸 “젤다의 전설에 나오는 녹색 애가 젤다지?”라고 물어봤기 때문이다.

링크가 녹색 옷을 입은 주인공이고 젤다는 그냥 잡혀있는 공주인데, 게임 타이틀에 젤다가 나와있다고

자꾸 사람들이 이렇게 착각하니까 정신병에 걸릴 위기에 놓인 것이다.

하여튼 젤다…아니 링크는 이 동굴의 반대편 출구, 제일 오른쪽 아래 칸인 [N-1][N-1]까지 이동해야 한다.

동굴의 각 칸마다 도둑루피가 있는데, 이 칸을 지나면 해당 도둑루피의 크기만큼 소지금을 잃게 된다.

링크는 잃는 금액을 최소로 하여 동굴 건너편까지 이동해야 하며, 한 번에 상하좌우 인접한 곳으로 1칸씩 이동할 수 있다.

링크가 잃을 수밖에 없는 최소 금액은 얼마일까?

입력

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

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

(2 ≤ N ≤ 125) N = 0인 입력이 주어지면 전체 입력이 종료된다.

이어서 N개의 줄에 걸쳐 동굴의 각 칸에 있는 도둑루피의 크기가 공백으로 구분되어 차례대로 주어진다.

도둑루피의 크기가 k면 이 칸을 지나면 k루피를 잃는다는 뜻이다.

여기서 주어지는 모든 정수는 0 이상 9 이하인 한 자리 수다.

출력

각 테스트 케이스마다 한 줄에 걸쳐 정답을 형식에 맞춰서 출력한다.

형식은 예제 출력을 참고하시오.

예제 입력 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

예제 출력 1

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

추가 반례

예제 입력 A

25
7 8 7 6 0 1 5 3 4 9 0 0 7 2 9 7 0 4 2 7 5 0 5 2 4
0 0 9 6 1 2 2 1 1 2 9 2 0 7 6 6 7 1 6 4 4 0 4 1 1
9 0 3 9 2 5 1 2 9 8 4 6 8 2 3 8 7 9 5 5 2 0 9 5 4
9 8 0 4 0 6 7 1 4 7 7 8 6 7 6 0 5 7 4 6 1 9 4 2 6
0 3 7 5 7 2 9 2 8 7 4 2 8 9 6 9 6 2 4 2 0 9 9 5 2
3 8 4 2 9 8 2 0 2 1 8 2 8 6 5 2 9 2 1 1 9 5 9 0 2
5 6 3 9 4 6 6 7 9 9 1 5 5 7 0 8 4 8 5 9 9 6 7 3 4
4 5 0 6 9 4 5 3 8 4 6 9 6 7 5 8 5 5 5 7 9 7 7 1 4
6 6 6 9 4 2 5 8 8 5 0 3 0 7 7 3 3 7 4 5 0 2 0 4 7
3 3 7 2 5 6 3 3 7 0 2 0 2 6 2 6 7 5 6 8 5 2 8 1 9
5 7 5 8 2 3 5 2 7 9 7 0 2 1 1 4 4 9 2 1 2 1 4 2 3
2 7 8 9 6 9 6 0 8 0 4 0 2 2 3 3 8 1 7 0 2 4 2 2 9
5 4 0 5 6 4 2 3 9 2 0 3 5 6 4 0 3 7 0 9 4 4 7 2 3
8 2 1 1 6 9 8 3 8 4 3 6 5 4 2 3 5 6 1 0 3 2 6 4 3
9 9 5 9 2 6 3 6 4 3 8 6 8 9 7 0 6 9 2 3 4 7 7 0 4
3 8 2 7 9 6 8 6 1 7 6 2 0 6 8 6 3 5 0 6 6 8 6 5 8
0 9 7 5 6 4 6 2 5 4 2 5 9 1 2 6 6 2 9 3 2 2 6 9 4
1 3 5 7 4 8 0 3 7 3 5 7 6 5 7 3 1 0 9 8 7 6 9 9 5
2 8 3 4 8 2 8 5 7 1 9 5 0 6 3 8 4 7 6 0 0 5 7 9 8
7 2 9 6 9 0 5 3 3 2 7 6 0 5 9 4 6 4 6 0 0 2 0 2 8
0 4 8 6 1 3 7 7 2 9 5 9 1 8 7 6 8 0 5 1 4 3 7 1 7
7 0 9 4 5 5 7 8 5 7 8 1 2 6 0 7 9 6 9 8 0 4 5 5 1
8 8 5 1 8 3 3 4 7 7 1 0 6 6 3 6 3 2 1 0 5 0 5 0 7
3 2 1 6 8 9 7 9 7 8 0 1 6 7 5 0 5 6 3 3 3 4 1 5 9
1 3 6 8 5 7 1 6 3 0 1 5 0 7 1 0 8 7 3 7 0 2 1 0 9
50
5 5 1 4 5 2 8 6 5 8 6 6 8 8 8 0 5 9 2 5 7 2 8 9 8 0 7 0 7 7 5 8 1 2 5 2 0 1 9 4 3 1 6 5 7 3 0 4 6 3
7 1 1 7 2 7 5 0 2 2 9 9 5 5 7 4 1 2 6 1 1 3 8 4 2 5 5 7 4 5 0 4 0 6 2 5 9 6 3 6 4 5 1 1 1 0 9 8 9 3
9 8 2 7 4 5 8 7 9 0 5 9 9 8 6 2 1 4 2 4 8 4 3 4 5 2 0 1 9 5 5 8 5 1 5 0 1 4 6 9 6 0 7 9 3 5 2 1 6 9
3 3 3 2 1 6 1 1 9 4 2 4 8 7 4 7 8 6 8 3 0 6 6 7 5 9 0 7 6 8 0 5 4 1 0 3 9 9 4 2 3 2 8 0 2 5 8 0 2 0
3 6 6 7 3 5 4 5 0 2 5 2 0 1 0 5 3 7 4 4 1 8 6 9 6 4 4 4 1 5 4 6 0 8 3 8 2 0 7 7 9 9 1 9 0 4 5 7 1 8
0 7 9 2 7 1 5 3 8 6 1 7 1 0 3 4 3 5 0 1 4 1 7 4 9 9 6 6 1 9 8 8 0 0 2 6 6 1 6 0 7 9 3 8 2 4 8 8 9 3
9 0 3 9 3 8 5 3 9 3 1 5 9 0 5 5 4 3 8 5 4 8 5 7 1 9 2 2 1 0 5 0 8 5 2 6 0 9 2 3 2 8 7 9 5 4 1 4 0 8
3 7 0 2 4 7 6 9 2 1 2 6 2 5 2 1 9 2 7 7 2 4 5 2 0 6 6 4 3 6 1 9 8 3 4 9 8 1 3 8 7 3 7 6 4 1 3 7 5 3
5 6 1 7 7 6 7 4 8 7 9 1 3 7 0 9 2 8 7 8 8 7 8 6 6 3 0 0 9 3 5 0 3 4 9 0 1 7 7 9 1 1 5 4 9 9 2 5 1 0
1 3 5 5 9 4 5 1 1 3 5 4 6 0 3 8 0 4 9 9 6 3 0 4 5 4 1 1 4 3 4 9 0 1 5 8 3 1 2 3 3 0 8 9 5 3 0 3 6 8
1 9 8 6 5 9 7 9 3 0 4 2 5 9 8 9 7 1 2 1 4 1 7 1 8 7 1 2 8 1 1 7 4 6 8 3 7 4 0 0 3 3 5 2 2 3 9 3 7 5
3 1 7 1 6 1 3 8 8 1 3 4 7 4 9 4 1 6 1 5 0 5 3 7 2 3 5 5 7 0 0 7 0 7 3 4 2 9 0 8 1 6 0 8 4 6 6 1 0 5
2 7 8 4 9 3 6 9 1 6 4 3 3 1 4 7 7 6 5 5 4 3 9 7 7 1 5 0 5 6 2 0 1 0 5 0 1 9 4 6 3 8 8 3 0 2 1 1 4 5
0 2 5 0 1 7 7 8 0 6 7 3 9 1 1 4 1 2 5 1 0 5 9 3 2 3 5 7 6 7 6 9 4 9 8 1 5 0 0 1 8 5 5 0 1 7 2 2 3 6
1 8 8 4 3 7 0 3 5 4 5 6 9 6 9 5 8 3 2 8 6 1 3 6 5 1 5 0 2 8 7 7 0 5 7 9 2 8 3 0 5 8 9 4 9 7 7 7 3 0
2 1 7 8 0 7 4 0 6 2 4 2 7 6 4 9 2 6 0 7 9 2 3 0 3 1 7 7 4 6 1 3 4 7 1 6 9 1 1 3 9 7 3 1 3 0 2 1 0 5
9 3 1 7 4 4 8 5 0 4 5 2 5 7 9 9 9 0 1 6 4 8 4 9 3 3 6 0 7 9 7 5 5 8 9 7 3 5 3 6 8 2 8 8 4 4 4 3 2 8
1 8 4 5 4 6 8 6 4 3 7 8 0 8 8 6 3 2 4 8 3 7 3 9 8 5 5 5 0 3 5 2 7 6 7 6 7 5 2 6 6 1 2 1 8 4 2 1 9 5
3 3 1 4 6 7 5 8 8 5 9 1 9 8 9 5 5 7 5 0 0 5 2 7 1 6 0 9 7 1 6 8 9 1 4 7 2 7 6 0 9 7 7 3 2 5 1 7 2 8
3 7 9 8 9 2 7 5 4 1 2 7 3 0 7 5 5 6 7 4 9 1 9 3 1 5 4 7 1 6 2 4 7 8 3 2 5 9 4 9 4 1 2 3 2 8 1 0 0 9
7 9 0 8 7 2 5 9 6 4 5 8 3 1 7 9 4 5 8 9 1 4 9 9 4 0 9 2 3 4 6 9 4 2 1 0 7 9 1 8 4 5 3 6 0 1 8 7 1 5
0 0 7 8 0 3 1 2 5 7 0 1 5 4 1 5 4 0 9 2 0 2 0 2 3 1 8 9 9 8 9 6 5 3 4 5 2 9 4 7 7 4 1 6 2 0 1 6 3 3
4 2 4 9 4 7 9 5 3 2 9 4 0 6 1 6 8 3 8 1 9 4 5 8 5 7 7 5 4 6 6 7 5 8 6 6 1 6 6 8 3 0 3 7 0 4 4 5 6 2
9 3 6 6 4 0 6 0 5 5 0 0 9 1 3 6 7 3 2 6 5 2 0 0 7 3 7 5 4 8 7 6 6 6 0 2 1 7 4 7 3 0 8 7 4 7 4 3 6 9
9 0 2 8 6 5 2 5 0 8 1 1 7 5 5 8 6 7 4 2 0 8 0 8 3 7 7 1 0 0 5 6 9 8 6 3 3 4 8 7 2 3 1 9 1 9 8 5 0 0
2 7 7 5 0 4 5 6 0 5 2 7 2 0 6 4 9 3 8 2 4 8 5 0 6 6 7 2 6 7 2 6 7 7 4 4 5 4 4 0 8 7 5 7 8 5 6 0 2 0
6 1 5 7 9 1 5 0 9 2 5 0 5 8 2 1 7 9 4 6 4 5 3 6 5 5 2 4 4 4 7 9 1 7 2 1 0 9 6 7 9 3 6 5 3 9 5 8 4 4
4 7 8 4 2 2 1 7 3 9 9 0 1 8 1 7 7 4 1 3 6 8 7 5 3 2 8 8 7 3 6 9 1 3 3 6 7 2 2 8 8 9 3 5 4 2 5 2 5 7
7 0 9 3 3 2 7 3 5 2 0 8 3 4 5 7 7 6 3 1 4 7 1 6 0 2 8 0 4 9 9 6 8 4 0 3 1 3 8 6 9 4 4 2 4 1 9 5 0 0
0 5 7 8 6 0 5 1 7 8 7 1 8 2 5 5 5 7 1 4 7 5 8 9 1 0 6 6 2 7 6 2 7 9 4 4 8 6 8 6 7 9 8 2 6 2 4 9 0 4
9 3 7 0 4 3 7 0 3 7 1 1 8 0 5 6 0 4 0 2 1 9 8 6 3 1 5 4 5 9 5 9 4 3 7 2 6 8 0 3 0 5 2 8 9 7 0 5 1 9
5 6 1 1 4 8 3 4 6 9 5 5 0 1 4 9 4 9 8 1 8 3 5 0 2 4 5 6 4 7 9 2 7 4 9 2 3 0 9 8 6 8 2 5 1 2 4 8 3 1
5 8 9 1 9 0 5 0 2 8 3 1 1 9 7 4 5 2 5 3 5 8 0 5 9 2 2 1 1 0 3 8 3 6 0 1 8 8 2 3 1 3 3 0 4 0 3 2 1 4
9 6 6 6 1 6 7 8 3 9 5 8 7 4 6 3 3 8 3 3 3 6 5 7 6 2 0 0 0 2 6 4 7 3 6 2 1 7 7 5 0 8 4 3 8 8 9 9 9 5
3 3 5 7 8 8 0 8 4 8 8 5 4 4 6 9 5 4 2 6 4 3 9 7 1 9 1 8 5 8 4 6 4 3 3 7 4 9 5 9 9 1 4 9 3 6 6 5 5 2
7 0 3 5 6 8 1 3 3 0 0 2 5 4 3 2 8 8 8 2 3 4 5 2 5 2 4 5 0 1 2 2 9 9 6 6 9 3 5 8 8 0 2 8 8 2 8 5 6 2
2 7 5 0 2 3 8 1 6 7 4 4 0 4 3 5 3 9 6 5 9 6 5 6 0 9 8 1 2 7 1 1 2 1 9 7 9 6 8 1 5 4 9 2 2 8 1 2 0 8
2 9 7 0 4 7 6 1 6 8 3 8 7 7 1 6 0 4 7 6 2 8 7 3 2 9 9 4 6 7 7 8 3 5 8 5 8 1 0 0 2 5 7 0 6 0 8 8 2 8
1 0 7 3 1 6 3 0 6 0 1 6 0 0 0 9 9 3 5 2 9 0 5 5 2 6 9 7 5 8 6 8 7 5 8 8 3 2 5 6 5 6 7 5 1 2 4 3 0 5
0 2 8 9 4 1 4 0 1 8 8 0 8 7 9 8 8 9 6 3 9 7 2 2 0 8 3 4 7 2 3 8 2 9 3 4 5 8 3 6 3 5 0 6 6 3 4 7 5 7
8 9 3 7 5 6 5 3 4 9 2 5 0 5 4 8 6 5 4 5 9 8 0 3 3 5 0 9 7 3 0 8 5 0 5 6 9 2 2 0 4 4 8 4 5 0 5 3 8 3
7 9 2 5 9 1 2 7 4 4 6 9 3 3 0 2 4 7 4 6 8 7 1 4 9 5 2 8 0 2 9 8 4 1 6 6 0 7 3 6 4 7 3 3 7 1 2 0 7 9
2 5 6 1 2 6 5 9 8 0 2 1 1 2 2 3 8 4 2 4 4 2 8 7 3 2 2 9 3 3 0 4 9 1 8 6 2 1 4 4 0 6 2 8 5 5 0 6 6 7
3 8 4 7 2 8 9 7 1 4 7 1 6 2 0 4 0 0 3 4 2 8 8 1 7 3 0 3 6 5 9 4 1 2 7 4 6 9 0 6 0 8 3 3 8 0 7 7 5 2
0 3 3 5 8 0 6 5 8 8 3 4 4 6 5 6 4 2 6 1 8 6 9 8 7 0 0 2 8 3 3 4 1 4 3 6 4 1 0 2 5 0 8 0 3 3 1 7 0 3
8 1 7 2 1 6 0 5 3 6 6 7 6 3 8 8 3 9 0 9 0 8 0 4 7 1 9 2 1 2 3 9 4 8 8 2 4 4 6 8 9 5 4 5 3 0 8 5 2 7
8 3 1 1 9 5 9 1 4 8 6 1 1 8 0 1 0 7 2 8 3 5 7 5 7 0 5 3 6 8 6 5 5 1 7 9 3 4 8 5 0 9 7 2 6 9 2 6 5 4
4 7 0 8 5 1 8 5 7 6 6 1 2 0 7 4 5 5 1 8 6 6 7 8 9 0 7 0 7 6 4 1 7 3 4 4 2 1 0 4 3 4 2 4 2 2 3 7 5 1
3 1 9 0 5 2 3 6 5 5 9 4 4 9 2 3 1 8 8 6 0 2 0 9 9 4 9 8 6 0 3 1 7 5 9 2 6 1 6 0 2 9 3 4 3 3 6 4 5 1
7 9 9 2 9 5 7 1 9 6 4 6 4 5 3 0 8 9 3 2 7 3 4 0 6 8 1 0 5 5 1 3 7 0 1 5 7 8 2 9 3 0 0 8 2 1 8 2 2 2
100
0 0 2 2 8 4 4 9 2 0 5 2 4 9 5 7 5 5 6 8 3 9 3 5 0 2 7 3 1 3 9 6 9 9 1 4 6 5 4 6 7 5 9 7 1 5 1 5 8 2 2 1 2 1 6 1 7 3 1 5 9 6 3 4 7 2 6 7 9 3 0 3 9 9 8 6 1 6 3 6 5 8 5 5 4 1 5 2 7 4 8 6 7 0 8 8 2 4 3 4
1 0 0 2 0 7 6 0 2 4 6 3 3 3 5 1 7 0 4 6 7 2 2 5 2 4 8 7 4 3 6 2 5 2 9 7 2 7 8 8 5 6 8 4 4 7 4 8 0 1 2 1 1 1 6 9 4 7 1 4 5 1 3 7 2 3 6 4 7 5 8 4 8 3 5 5 4 0 5 1 2 8 4 6 4 9 6 1 1 7 8 4 9 9 5 8 4 3 1 8
2 5 0 0 2 8 8 0 6 7 7 5 6 0 7 2 8 9 1 2 1 3 8 2 5 7 8 6 4 4 7 7 8 0 1 8 4 8 9 5 0 0 6 6 0 0 7 9 1 5 5 7 6 8 0 2 4 3 1 6 2 8 2 3 8 6 8 4 2 9 3 9 0 3 7 3 8 6 5 4 6 7 6 4 0 4 5 9 4 0 6 5 0 0 2 2 1 3 4 4
1 1 9 0 0 7 2 2 3 3 2 7 4 5 2 4 0 8 1 3 5 8 4 6 4 7 4 4 4 2 5 3 8 5 0 2 6 2 7 9 0 8 7 3 1 6 1 8 7 1 0 2 1 7 7 4 4 9 2 4 7 9 5 5 9 3 2 7 7 1 0 0 8 0 3 2 5 3 1 5 4 3 7 8 9 9 9 7 6 7 2 1 1 7 6 5 4 3 9 1
4 8 3 7 0 0 7 7 1 3 4 0 1 5 1 4 6 3 0 6 8 3 3 9 0 6 2 6 0 1 2 1 6 3 4 1 9 2 6 7 3 4 4 5 8 4 7 4 6 1 8 2 8 8 3 5 2 5 5 7 2 6 0 7 8 6 9 2 9 0 1 8 2 0 3 5 0 7 7 6 6 5 3 7 8 9 3 7 8 9 5 7 0 1 4 7 8 7 8 5
4 7 5 2 6 0 0 5 3 5 6 0 8 8 5 4 7 3 9 4 0 1 2 8 2 9 9 7 8 5 5 9 6 0 7 2 3 0 3 8 1 4 7 6 0 4 6 9 9 5 0 8 3 9 3 9 7 2 1 5 3 4 0 1 7 4 0 6 4 6 1 7 0 8 5 3 1 8 6 8 9 7 4 4 9 3 0 5 8 1 4 2 5 9 7 4 2 5 7 0
8 4 6 4 7 0 0 0 7 6 3 3 6 1 8 7 0 0 0 3 0 3 1 2 6 2 0 8 8 8 3 2 5 4 8 2 2 5 2 7 5 8 7 8 4 8 3 1 4 8 7 2 3 2 9 9 3 9 7 4 7 4 0 4 7 6 0 8 9 0 8 7 1 2 7 2 7 9 0 2 9 5 8 3 1 1 3 1 2 5 8 7 8 3 1 8 5 0 6 3
0 9 7 5 3 2 8 0 0 5 2 9 6 0 5 2 3 5 9 2 9 4 8 8 8 0 0 8 5 0 1 4 8 1 4 1 6 5 4 4 8 1 8 6 8 9 1 8 6 4 6 4 4 4 3 2 1 6 0 9 9 9 4 0 2 5 8 8 1 4 0 2 1 3 3 3 6 2 1 8 6 7 0 8 9 5 2 7 4 8 5 7 0 8 3 4 5 1 7 9
0 5 2 6 0 0 6 8 0 0 9 3 5 3 3 2 0 4 9 4 3 8 0 6 5 4 4 8 9 8 3 8 1 9 4 3 6 3 2 3 7 0 7 2 7 4 6 4 6 9 7 2 6 1 0 7 8 5 3 1 4 5 5 3 7 9 6 3 3 2 3 8 0 8 7 9 6 3 1 6 1 2 6 6 9 8 8 7 5 9 6 4 6 3 4 8 2 6 1 9
1 3 4 4 5 2 9 7 4 0 0 0 5 8 4 1 4 7 2 4 9 6 7 3 9 8 3 9 9 2 9 4 3 1 7 9 2 0 5 9 8 3 4 7 3 1 5 9 5 5 0 1 6 5 6 3 5 0 8 1 4 1 5 3 0 2 5 7 7 8 7 6 5 1 4 1 1 9 9 5 9 8 7 6 2 1 6 7 3 0 0 8 7 9 1 1 0 2 0 2
6 2 8 1 2 3 7 4 9 0 0 0 2 1 2 4 3 5 0 0 9 0 9 2 7 9 3 1 8 5 5 8 4 8 7 8 3 3 4 8 6 7 4 9 1 1 1 1 5 3 0 5 0 8 0 1 3 7 7 7 1 9 2 6 0 9 4 6 6 2 7 9 3 9 5 7 9 2 4 6 2 7 5 5 3 4 3 1 1 9 4 2 9 6 6 2 8 0 0 8
9 4 8 8 5 6 7 8 2 4 6 0 0 7 0 1 2 4 3 3 5 6 8 1 8 0 5 6 1 6 9 5 9 9 2 3 1 2 3 7 3 8 6 3 5 4 9 5 7 2 7 3 8 0 2 8 1 1 8 4 7 7 2 6 3 8 1 5 1 1 0 5 7 6 7 5 7 2 3 2 9 6 0 5 8 4 4 9 1 9 4 0 6 7 3 5 4 4 9 7
7 3 4 9 8 8 7 9 0 1 8 3 0 0 5 9 9 2 6 1 2 6 4 8 7 8 1 1 4 4 9 8 7 7 0 8 0 3 1 8 2 8 8 0 2 2 9 9 2 3 5 4 3 4 9 7 5 9 2 3 5 9 1 7 3 1 7 5 2 8 7 2 0 3 7 6 2 2 7 0 8 4 7 5 0 6 8 5 2 9 4 4 3 9 2 0 8 5 7 9
1 7 0 8 6 8 6 3 3 2 6 4 5 0 0 1 7 6 8 6 0 9 7 1 0 6 9 8 6 2 9 4 1 7 6 2 8 1 1 2 6 2 7 7 1 1 6 8 4 2 9 0 4 3 7 3 0 5 3 3 5 0 1 1 7 5 2 7 7 9 9 7 0 8 2 5 5 3 2 5 3 3 0 3 4 7 0 9 4 5 2 2 2 5 3 5 7 7 7 7
5 3 4 0 7 2 2 0 3 3 8 4 8 4 0 0 4 3 0 5 2 1 0 1 8 6 3 4 7 0 0 7 0 6 1 2 7 9 7 9 5 9 1 5 7 9 3 1 7 7 9 0 5 0 4 9 5 3 5 5 1 9 6 6 4 0 6 3 6 5 0 8 2 3 9 8 6 3 5 4 8 0 9 3 2 2 5 9 3 8 5 0 3 3 4 0 7 3 0 4
6 0 5 8 3 6 4 5 9 3 2 3 9 3 2 0 0 6 2 9 9 6 5 9 7 3 7 3 7 9 9 1 9 1 7 0 4 9 8 1 3 0 4 0 8 0 0 2 3 5 6 5 5 3 1 6 4 1 4 8 5 5 5 4 2 3 2 7 5 1 9 8 6 3 0 4 8 5 2 8 2 1 1 9 7 5 1 5 5 5 8 9 3 8 0 0 2 0 5 8
3 1 1 9 7 6 5 3 3 0 6 7 6 1 3 3 0 0 5 3 9 4 5 6 3 5 9 9 7 7 6 7 0 8 6 1 1 7 4 0 7 5 3 8 7 8 5 6 9 3 5 8 4 3 5 3 2 0 4 8 9 1 4 9 5 9 3 7 4 9 4 8 7 7 1 4 1 0 8 6 4 5 1 7 6 3 1 4 0 3 6 1 4 5 0 4 0 5 5 4
6 4 0 0 0 0 3 4 8 4 5 9 1 9 2 5 2 0 0 3 1 4 7 7 2 2 3 8 7 0 8 0 0 6 9 2 6 0 5 0 0 9 2 9 7 1 8 9 4 5 1 2 2 3 6 5 3 2 8 6 4 0 5 0 3 5 0 7 5 0 8 7 9 1 6 5 6 7 4 6 9 8 7 8 2 5 3 1 2 0 6 4 3 7 6 3 1 4 6 1
8 6 5 2 3 5 0 1 9 3 6 2 4 0 4 9 5 3 0 0 1 0 8 5 1 7 9 0 1 8 4 3 9 8 4 6 5 2 1 4 6 8 5 0 1 2 0 3 9 6 9 1 1 3 4 4 7 9 9 0 2 6 9 6 3 1 1 4 7 8 5 3 9 9 1 1 9 5 9 1 7 6 2 3 1 8 2 7 0 9 2 9 6 6 2 6 8 1 8 2
0 2 9 1 3 1 5 6 4 7 4 5 6 3 5 7 5 5 3 0 0 1 5 4 1 5 6 6 0 4 5 5 2 5 9 1 5 8 0 4 1 8 8 0 4 9 4 0 8 9 3 6 2 2 6 8 0 6 3 7 0 9 2 6 6 1 4 3 9 8 4 9 0 2 0 8 3 9 9 7 5 9 2 7 2 0 3 2 4 1 0 9 1 8 3 8 9 5 7 2
5 5 1 6 4 7 7 5 6 8 2 8 0 6 1 3 6 8 8 9 0 0 5 6 9 5 1 6 9 2 7 0 2 7 7 4 2 2 0 5 1 1 2 2 7 4 4 4 9 8 3 7 6 4 5 7 2 5 5 2 5 1 1 1 4 3 4 2 8 0 0 5 6 6 0 2 1 2 0 8 8 6 0 7 2 9 4 7 1 6 7 3 7 1 7 6 2 7 8 5
5 8 0 5 6 5 6 2 3 3 6 1 5 8 3 0 9 7 7 4 2 0 0 4 2 8 2 9 0 1 7 6 3 4 7 6 0 2 7 5 1 7 3 2 8 2 0 3 3 9 3 9 2 2 0 2 8 0 0 3 6 2 0 9 0 1 7 6 6 0 3 5 3 5 9 9 0 6 8 9 1 0 3 8 5 4 4 4 6 6 8 7 5 6 8 7 7 4 1 5
6 5 9 6 8 8 8 2 1 0 9 3 4 2 6 2 9 4 4 2 7 1 0 0 5 2 7 1 7 0 1 4 6 7 1 4 9 6 7 1 1 1 2 4 2 0 1 5 9 4 5 3 7 8 6 7 3 2 0 0 3 5 0 3 3 1 6 7 0 8 5 8 7 2 7 6 8 6 1 2 8 1 9 8 1 0 5 2 8 8 7 3 1 1 6 3 4 5 8 4
8 9 2 8 2 9 7 4 4 5 7 4 4 7 8 4 9 9 1 2 0 1 7 0 0 8 0 4 5 5 5 9 4 5 2 9 8 6 6 3 4 6 6 3 7 8 4 6 7 3 1 1 9 7 4 2 7 5 8 2 0 5 7 9 6 7 2 7 5 4 3 3 4 7 1 9 6 7 9 9 0 3 8 1 3 6 9 0 3 2 8 5 8 0 4 9 2 6 7 6
4 3 3 9 2 7 1 1 7 0 7 2 5 2 0 4 7 2 8 7 5 1 1 0 0 0 2 8 3 2 4 8 1 0 0 4 8 5 6 5 6 5 2 1 5 3 5 2 1 1 3 8 8 7 9 9 0 5 7 3 2 2 1 5 6 3 3 7 0 2 5 0 4 7 0 9 4 3 0 7 6 6 2 0 8 9 6 9 4 6 5 8 7 9 9 8 8 8 1 1
6 4 4 2 4 0 3 5 2 4 8 4 7 6 1 9 0 5 7 5 0 2 0 6 5 0 0 9 2 8 0 1 6 8 4 7 4 2 5 3 6 3 4 3 9 7 2 0 3 4 3 2 5 7 2 8 3 5 3 0 2 3 0 8 5 3 7 5 8 8 6 8 3 9 7 4 9 7 5 4 7 9 0 6 6 8 4 5 5 0 0 7 6 3 4 2 7 3 0 5
1 6 9 9 4 0 1 8 4 6 2 7 8 7 4 4 9 2 8 0 1 9 6 4 1 0 0 0 3 3 8 6 5 2 2 5 5 1 4 9 2 0 5 4 9 3 2 4 4 0 1 1 6 3 6 4 3 1 1 3 2 4 0 8 2 3 2 5 0 3 9 0 7 4 6 1 7 3 0 2 8 6 9 7 5 8 7 3 9 0 6 0 0 2 6 7 9 7 5 2
0 0 3 5 2 6 6 4 8 0 4 0 2 6 1 6 6 4 6 1 2 7 0 2 7 6 0 0 0 6 4 1 4 7 7 2 4 0 3 4 1 8 7 4 2 2 1 6 8 4 4 6 8 3 2 9 4 9 1 0 2 9 9 0 0 1 7 3 1 5 2 0 5 2 3 3 4 8 0 7 4 7 8 4 7 6 6 0 2 7 8 1 2 0 9 0 0 6 8 5
1 3 7 0 4 7 1 7 6 9 5 1 8 8 5 2 1 6 9 4 5 7 1 0 8 9 1 8 0 0 5 4 0 5 3 8 1 3 7 0 5 4 8 7 8 4 4 6 9 1 1 2 4 6 6 7 6 0 3 3 8 5 5 7 5 3 4 6 8 7 3 6 4 6 7 3 9 9 2 2 1 0 5 7 8 9 8 6 7 5 3 4 3 0 8 2 5 1 1 3
9 0 2 9 7 3 6 2 4 4 4 8 9 0 1 1 1 2 8 7 1 5 7 5 1 9 6 5 6 0 0 0 2 9 8 2 8 1 5 3 9 9 3 8 2 4 7 1 3 0 5 7 2 5 9 7 5 9 2 3 2 3 6 3 5 4 5 1 4 4 6 0 5 1 2 7 9 8 5 6 9 6 5 6 3 7 3 7 3 6 6 2 8 4 6 6 2 0 0 0
1 9 1 2 4 5 7 9 9 2 7 9 4 8 9 6 9 7 3 2 3 5 8 8 3 9 9 0 2 0 0 0 3 5 0 2 6 9 7 8 1 2 3 1 2 9 1 9 4 5 6 9 8 1 6 9 1 6 5 1 5 2 6 4 9 7 1 3 3 3 4 4 1 7 1 6 4 4 0 7 2 7 9 8 7 3 0 7 6 4 8 9 8 3 7 5 0 5 7 8
9 3 4 3 1 6 9 7 1 5 4 7 6 8 0 0 8 3 5 8 8 0 8 7 8 2 1 4 8 1 5 0 0 9 0 9 3 0 9 1 7 1 6 5 6 6 4 6 4 6 1 8 6 3 9 9 7 3 5 8 7 7 1 6 5 6 4 9 1 9 1 7 6 9 7 5 1 5 2 7 2 5 0 8 3 3 1 8 0 1 1 7 6 0 2 6 7 9 2 7
4 7 3 2 3 1 2 7 3 6 6 0 4 4 3 4 5 6 1 0 6 5 6 9 7 4 0 3 1 3 3 1 0 0 7 4 7 0 4 3 0 7 9 3 6 6 7 4 4 3 4 0 5 1 3 9 5 9 1 2 1 8 8 5 2 0 8 4 0 5 4 1 1 9 7 7 3 2 9 6 6 4 2 9 9 2 3 9 1 2 9 4 5 7 6 1 6 6 0 8
1 2 1 4 8 4 8 3 2 0 5 2 8 7 4 1 9 5 6 7 6 3 3 2 2 7 6 0 4 5 2 0 6 0 0 6 0 4 4 6 7 5 2 9 9 2 4 5 0 0 1 5 9 0 5 8 1 2 5 0 9 7 5 6 3 2 0 1 0 4 3 1 5 6 1 7 7 7 3 9 4 0 3 9 3 1 2 9 4 1 4 3 1 4 3 4 6 4 6 2
6 4 1 1 6 3 3 8 3 1 9 5 4 8 1 5 3 5 8 4 5 5 1 1 1 2 5 7 4 1 7 2 4 2 0 0 3 1 3 2 3 1 7 3 2 1 0 1 4 9 9 3 3 7 9 0 0 5 2 7 8 2 1 7 2 8 4 9 1 9 0 1 9 5 3 5 4 9 3 0 5 0 3 5 3 1 2 4 3 4 4 3 7 6 1 2 7 2 5 2
0 8 2 8 4 9 7 4 4 3 3 4 2 6 3 6 3 3 5 6 3 3 5 2 4 8 3 3 4 3 7 7 4 4 7 0 0 3 9 6 0 4 7 1 2 3 9 9 2 3 6 0 5 2 1 9 1 6 0 4 7 2 4 8 4 0 1 0 6 1 1 8 6 8 0 9 9 7 2 2 7 6 0 4 3 6 6 5 1 2 8 5 6 9 6 4 1 9 8 3
1 6 3 1 7 8 5 8 5 5 6 6 2 6 1 4 1 9 6 8 4 9 2 1 5 6 3 2 7 3 1 0 4 9 9 0 0 0 9 3 9 4 1 8 1 3 7 6 3 3 7 7 1 4 0 6 5 1 4 9 7 1 9 0 8 8 3 6 6 3 9 8 8 9 9 0 5 2 3 7 5 7 9 5 3 0 6 4 3 8 3 4 9 6 5 1 2 6 8 7
1 5 4 5 6 8 7 1 9 8 9 7 7 9 2 2 0 4 5 3 1 0 9 0 6 0 1 5 5 8 2 8 7 2 6 8 1 0 0 8 7 0 9 2 1 5 5 1 0 8 0 5 3 3 9 8 7 6 2 0 2 9 8 0 3 0 4 3 0 4 6 2 4 5 0 6 6 6 0 2 4 2 2 3 4 5 5 2 8 3 0 0 8 1 2 3 7 8 0 1
9 7 5 2 2 5 1 5 6 2 2 4 5 1 4 1 7 9 4 1 5 9 8 9 8 8 4 6 2 1 5 4 9 7 4 6 6 8 0 0 3 1 5 7 3 8 7 9 4 5 5 2 7 3 6 2 8 4 7 5 7 0 7 0 6 7 3 1 9 1 1 9 4 4 2 1 7 0 4 7 5 5 4 6 3 4 9 7 0 8 5 3 8 9 9 1 4 2 4 0
5 9 1 4 7 9 1 1 0 4 1 3 7 2 9 4 6 6 9 6 2 8 1 8 2 5 0 5 2 4 5 2 1 7 4 7 0 0 4 0 0 0 4 5 8 8 2 8 2 4 4 9 9 8 0 5 9 9 1 5 4 5 2 8 7 6 6 6 7 8 9 6 7 3 6 9 0 9 1 7 3 9 1 6 0 3 4 5 4 7 8 3 1 3 5 7 9 0 6 0
0 1 5 0 4 6 4 4 4 2 6 4 8 1 9 0 0 9 3 0 3 9 5 5 4 9 6 8 6 0 5 3 3 5 8 9 4 9 9 6 0 0 7 6 2 5 9 7 6 4 1 1 1 2 5 3 1 2 9 9 7 5 3 8 9 8 9 4 3 3 7 7 5 6 1 8 9 0 4 9 3 3 0 7 3 6 3 7 0 1 3 3 3 5 5 6 8 7 9 5
2 3 5 6 8 4 3 8 1 1 1 6 3 6 4 7 9 9 7 3 3 6 7 7 2 9 1 4 2 8 2 9 6 9 0 5 1 3 7 7 6 0 0 6 5 3 9 6 6 3 3 3 9 5 7 9 8 5 5 5 3 5 3 4 1 4 3 1 8 1 0 4 2 3 0 6 1 5 9 6 8 8 6 4 8 0 4 2 8 0 6 9 4 7 6 9 7 3 1 8
5 1 7 4 1 4 8 0 7 4 2 4 3 6 3 4 4 2 1 2 5 1 7 5 0 2 3 7 5 2 3 6 5 3 2 6 8 8 8 7 2 8 0 0 2 3 3 5 3 3 2 5 3 0 9 3 3 0 8 8 8 8 1 1 3 9 6 2 3 3 0 6 9 1 4 0 6 5 2 8 7 5 4 2 1 3 7 5 8 6 7 9 8 2 3 4 5 9 1 5
1 9 1 2 8 8 8 0 4 3 5 3 0 5 5 0 2 0 8 6 7 2 5 1 4 2 8 7 5 4 9 7 1 7 9 8 7 9 1 0 6 5 2 0 0 3 9 7 3 8 5 4 2 0 2 7 0 7 5 9 4 6 4 4 9 3 9 0 3 4 4 9 4 5 4 3 2 1 8 0 3 8 3 8 2 5 1 4 9 2 8 8 5 1 2 6 0 9 9 5
6 4 7 5 6 2 9 0 3 9 4 6 6 6 7 4 9 3 7 7 0 2 7 6 1 4 7 3 7 5 8 7 6 7 8 7 2 7 2 1 5 6 3 8 0 0 8 4 2 2 4 3 9 5 1 0 3 3 7 8 4 4 5 9 8 1 4 0 2 4 6 4 5 3 9 7 5 5 7 6 6 4 3 0 4 5 3 4 2 6 8 3 1 1 1 7 1 3 7 6
9 4 6 2 1 7 0 0 2 5 0 1 5 8 3 3 4 0 0 6 2 0 0 1 7 3 5 0 3 9 6 0 5 8 9 9 5 4 8 3 5 0 8 1 7 0 0 5 8 3 4 2 3 3 3 7 9 2 0 7 8 9 7 1 3 7 4 3 3 5 1 1 3 4 9 3 2 8 0 0 4 8 8 2 4 5 3 3 7 5 1 8 0 0 8 8 2 2 2 0
6 9 5 5 2 2 8 3 3 7 7 9 9 7 7 8 6 7 4 8 1 0 7 3 2 4 9 0 6 7 6 6 7 4 2 8 9 9 1 3 6 7 9 8 9 7 0 0 4 1 8 4 8 4 5 4 9 7 0 4 1 6 7 4 8 2 3 1 5 6 5 8 5 7 9 3 1 3 9 5 5 9 4 3 1 6 2 3 3 8 4 9 2 8 1 8 9 0 6 1
0 8 3 0 6 3 0 5 4 8 3 1 8 4 8 9 7 8 3 1 9 1 1 1 2 8 4 0 3 0 0 4 5 5 4 3 7 7 8 9 4 9 0 8 5 4 1 0 0 4 6 2 9 6 6 5 9 9 5 0 8 4 1 9 4 7 1 3 6 7 4 1 7 0 3 5 4 3 8 5 6 6 8 6 1 0 5 0 6 8 6 6 2 6 0 7 1 9 7 6
8 9 1 9 8 8 3 3 2 8 3 6 8 8 9 5 6 1 4 3 6 9 3 9 3 6 1 2 3 8 9 2 5 4 7 3 6 9 3 2 6 0 1 6 7 0 8 4 0 0 8 7 1 8 5 9 5 5 0 0 1 1 0 3 5 4 7 6 7 4 2 5 4 0 9 6 5 8 3 5 8 8 1 6 2 2 0 6 2 9 7 8 0 5 3 4 1 6 5 5
8 8 2 8 2 3 5 9 3 7 9 3 8 8 4 7 1 5 9 8 6 4 2 6 8 0 1 5 6 6 6 8 2 5 5 7 8 6 5 8 4 2 0 9 4 6 4 9 6 0 0 3 7 1 3 5 7 6 7 6 7 4 2 1 1 6 4 1 1 2 7 5 1 7 4 0 1 1 5 5 7 8 7 8 7 3 6 6 1 2 9 6 3 7 6 2 7 4 7 2
4 0 9 7 5 3 0 7 2 3 0 2 6 3 2 1 2 8 3 3 6 8 8 2 1 7 6 2 1 4 2 7 9 8 1 7 1 2 7 2 7 4 2 4 1 9 1 2 2 5 0 0 2 6 4 8 9 6 8 6 4 2 4 7 6 0 1 2 2 5 0 4 6 4 1 4 1 5 5 5 4 7 3 5 4 0 8 5 6 4 6 6 8 1 5 9 2 6 2 7
5 9 6 7 6 5 9 9 5 9 3 8 0 9 0 4 4 9 8 3 4 6 4 2 6 2 6 0 6 6 9 0 8 8 0 3 1 6 4 2 1 2 8 3 6 9 4 7 9 0 9 0 0 8 2 1 3 5 2 6 0 9 6 4 9 7 9 1 3 0 4 8 5 1 1 1 5 5 8 1 0 2 1 7 8 0 0 3 1 7 4 4 0 3 4 8 4 9 1 9
3 0 2 3 2 2 9 4 8 1 4 1 5 9 2 4 5 1 5 3 0 1 6 8 8 0 6 7 8 5 0 8 4 0 5 2 5 8 2 6 5 8 7 5 6 6 5 7 8 5 1 2 0 0 8 4 1 7 0 4 6 0 7 5 6 6 1 3 9 4 3 7 2 8 9 6 8 0 8 8 6 2 5 4 3 4 9 4 4 0 9 9 9 8 2 6 5 2 1 0
4 7 4 3 4 7 0 5 2 5 9 5 2 1 1 2 8 5 2 9 1 4 5 5 3 1 4 5 8 5 6 7 2 5 4 1 3 8 3 1 3 6 3 3 0 8 7 9 3 0 6 5 0 0 0 0 4 2 1 3 9 0 6 0 0 6 7 7 1 3 6 9 5 6 9 3 4 9 4 2 6 4 2 1 4 5 6 6 4 4 0 0 2 6 8 8 9 4 8 5
5 6 0 1 4 1 5 9 3 7 4 4 4 8 9 0 3 1 3 1 7 0 1 0 9 1 0 9 9 3 3 3 4 7 5 6 1 6 2 0 0 8 6 2 0 9 2 3 9 5 3 9 3 5 0 0 0 1 8 8 1 2 4 1 0 1 5 3 1 4 4 4 1 8 7 0 8 9 9 9 6 7 0 7 5 1 7 5 1 2 2 6 1 0 6 3 3 5 4 9
4 7 8 2 0 3 7 9 0 9 4 4 8 5 0 7 7 5 2 2 0 3 8 1 5 5 1 6 2 6 2 5 2 6 7 0 6 0 8 2 9 4 8 3 3 7 5 2 4 2 3 8 3 2 4 0 0 4 9 6 3 4 5 3 7 2 4 7 5 4 6 8 0 8 5 0 3 4 7 7 9 6 3 2 2 3 4 5 1 7 9 9 5 2 4 0 1 2 1 4
9 2 1 8 7 8 8 5 2 7 4 6 4 5 1 8 1 9 8 2 9 9 2 9 2 7 9 3 6 1 3 3 5 2 7 8 7 3 9 3 6 9 2 6 8 4 4 0 2 0 8 6 8 9 8 0 0 0 1 5 7 3 9 2 0 4 4 3 2 1 9 6 5 3 7 7 9 1 1 5 2 0 8 4 5 0 9 3 8 8 2 5 9 2 8 8 6 2 0 0
3 5 4 5 5 4 6 3 8 8 1 9 1 5 0 4 9 5 4 6 9 7 6 1 4 9 4 5 5 1 1 6 5 0 5 9 7 7 1 6 6 9 5 9 9 4 2 0 4 2 1 9 7 4 8 4 2 0 0 1 7 4 8 8 6 2 3 4 7 7 5 2 8 6 7 7 3 8 8 0 2 1 8 6 6 7 0 7 5 3 0 6 3 0 6 1 4 0 7 4
3 2 2 6 1 3 4 1 2 2 4 2 8 3 8 9 9 4 7 9 3 3 3 6 4 0 7 9 4 5 6 2 8 6 3 2 7 2 6 5 0 2 5 6 2 0 9 9 0 3 0 9 6 4 2 1 4 0 0 0 5 6 7 0 3 4 2 5 6 1 6 2 5 5 3 3 3 0 4 4 9 5 5 5 3 5 1 5 9 6 8 6 1 9 7 6 0 4 1 2
0 0 8 2 1 8 1 1 2 3 1 0 7 2 9 0 0 4 2 3 2 8 9 3 1 0 3 2 9 2 0 8 6 1 3 4 3 5 9 3 1 2 2 1 3 4 5 4 8 8 2 5 2 2 8 9 8 4 0 0 0 3 5 4 4 4 6 2 2 0 6 8 7 8 2 9 9 4 5 5 4 2 9 7 3 6 9 2 0 1 8 2 0 7 8 2 7 4 6 4
8 0 4 7 6 6 5 7 9 1 3 3 6 9 7 6 9 0 2 3 9 1 2 9 6 8 3 3 2 9 5 3 3 4 9 3 5 4 1 3 8 5 4 0 7 7 9 5 0 1 9 9 0 2 4 9 2 9 6 6 0 0 1 9 2 3 3 5 2 9 9 5 4 1 9 5 0 4 3 2 3 9 8 1 6 9 3 8 4 2 5 6 4 3 7 8 3 0 4 9
0 0 2 5 3 0 4 0 5 5 4 4 5 1 5 4 1 7 5 0 9 9 8 8 0 4 4 2 4 8 0 6 6 7 3 7 8 1 5 0 4 2 0 3 8 9 4 1 2 5 3 5 4 9 3 0 6 2 0 1 1 0 0 1 8 9 9 1 0 4 0 8 4 5 4 5 2 7 7 6 2 5 5 8 3 6 7 7 4 6 9 9 4 0 5 0 7 7 6 0
3 5 6 2 8 0 2 3 2 9 8 4 9 8 4 5 2 0 2 8 5 1 8 8 7 8 0 1 7 7 0 2 3 6 5 3 2 9 5 7 8 5 3 6 1 3 2 4 7 6 5 4 3 6 4 5 2 9 3 3 8 8 0 0 1 5 6 9 8 2 8 6 4 8 2 6 5 6 2 7 9 2 0 4 5 8 4 4 6 3 3 8 9 1 4 5 3 1 1 6
1 5 8 7 6 1 0 4 6 8 9 6 3 8 6 4 4 1 0 5 8 9 4 5 5 6 0 6 8 7 5 1 0 4 8 1 8 2 3 5 4 2 6 9 7 8 5 9 4 5 7 2 5 7 5 3 7 4 1 7 7 7 8 0 0 3 7 3 0 9 0 7 4 1 8 9 7 9 7 9 4 1 9 3 8 7 5 6 5 8 3 6 6 3 6 4 1 8 6 7
8 4 9 9 4 3 6 2 2 9 4 0 4 6 3 5 8 8 2 3 9 6 7 1 3 9 3 6 7 7 0 2 8 1 7 4 7 8 5 0 8 4 4 4 6 5 7 4 1 8 9 1 9 1 2 8 0 7 1 3 7 2 2 6 0 0 2 8 2 8 3 5 5 3 5 9 3 7 2 8 6 1 8 3 7 6 3 3 2 6 4 5 3 3 9 7 4 6 7 0
9 2 1 7 2 4 9 4 8 0 5 5 7 7 5 8 1 4 1 2 5 8 2 2 0 2 8 1 0 3 9 8 4 4 3 7 6 9 4 9 8 7 7 9 8 6 6 9 2 5 9 8 7 7 3 3 3 0 3 5 9 2 0 6 2 0 0 5 3 7 0 7 3 0 9 1 2 1 5 3 8 2 7 5 0 4 9 4 8 3 7 5 7 3 2 6 0 5 6 7
5 6 3 7 1 2 0 9 1 1 6 0 4 6 7 3 2 9 0 6 6 5 2 9 0 7 9 0 6 6 6 7 5 0 3 7 1 2 3 9 0 3 1 9 9 9 5 9 7 7 4 1 6 7 5 1 1 6 7 9 3 0 0 5 6 0 0 0 4 2 9 3 9 4 6 7 7 2 7 2 7 8 5 3 8 2 8 1 3 6 2 7 3 1 9 6 8 0 6 6
3 6 3 3 6 7 5 2 6 4 4 4 1 6 8 2 0 2 4 4 6 3 6 5 5 0 1 6 1 0 6 9 8 6 4 4 2 9 8 5 1 9 5 8 8 6 5 2 9 8 0 1 6 1 4 2 4 8 1 2 4 7 8 5 1 8 7 0 0 5 1 2 5 2 5 2 1 7 5 7 0 3 1 4 3 3 3 1 0 3 4 9 3 9 5 0 7 8 6 7
2 7 6 8 7 2 8 8 1 2 6 8 7 0 2 4 6 6 1 5 7 2 1 8 4 6 1 9 9 0 8 3 2 7 0 3 7 9 5 7 9 6 7 2 7 0 4 8 8 0 1 2 4 8 3 2 8 2 5 8 3 4 3 8 7 2 7 3 0 0 4 9 3 6 4 5 1 7 8 0 1 7 8 5 4 8 5 9 5 9 3 6 9 0 4 2 9 2 8 1
0 0 8 5 8 5 0 3 3 8 3 1 1 3 2 5 1 0 0 0 7 5 1 8 4 4 7 6 1 1 1 3 1 4 3 6 0 9 6 7 3 1 0 2 1 6 2 5 8 9 9 5 0 6 1 9 1 8 5 8 9 8 7 8 2 2 6 6 5 0 0 7 6 3 8 9 8 9 4 6 8 1 7 3 2 1 5 0 8 0 3 6 9 8 6 6 5 3 1 7
0 3 8 6 3 5 0 6 6 4 8 2 5 9 2 2 7 1 7 1 2 8 6 4 2 4 3 3 6 9 0 0 3 6 6 9 2 1 4 3 1 1 4 4 3 0 0 9 4 7 7 3 2 5 6 8 3 6 7 2 9 5 4 3 9 2 4 0 6 8 0 0 7 9 4 9 1 2 4 3 3 3 7 5 0 6 1 3 4 1 8 9 8 0 2 6 1 9 9 0
5 7 5 2 1 6 8 0 2 1 2 4 4 7 3 4 2 9 5 5 1 5 2 1 4 2 5 5 7 9 8 1 5 5 1 5 8 9 8 4 8 3 2 6 6 7 3 3 3 9 8 0 3 1 1 8 6 9 4 6 5 9 1 3 2 6 3 5 6 6 0 0 0 4 0 1 9 9 1 2 2 8 1 4 6 3 9 3 0 5 7 9 3 5 3 0 8 3 0 4
1 1 4 4 5 4 7 7 1 6 4 6 3 9 7 9 9 5 0 7 4 0 8 1 0 9 3 2 1 5 6 3 8 5 8 2 3 3 3 1 2 8 8 2 7 1 7 8 0 0 4 4 5 6 2 2 3 9 3 8 3 6 5 8 4 2 6 8 8 5 0 3 0 0 6 3 5 1 2 7 5 0 8 3 6 3 0 0 2 1 0 0 6 7 8 0 4 4 8 5
7 2 1 1 5 6 0 0 3 9 7 1 3 9 5 7 2 3 9 5 7 6 4 5 6 7 8 2 7 1 0 0 9 8 1 3 6 9 1 3 3 6 0 1 0 9 9 5 9 0 7 5 6 7 8 8 0 4 8 0 0 9 4 2 4 1 9 4 3 5 5 9 4 0 0 8 1 9 5 2 7 3 3 1 4 4 0 2 6 5 5 2 3 3 1 1 9 1 2 0
8 2 6 2 7 2 5 5 1 6 9 6 5 6 9 3 0 9 3 2 1 5 8 1 0 8 9 8 6 5 3 9 3 2 4 8 0 8 2 8 8 1 0 0 4 9 8 1 6 2 3 8 4 2 2 7 6 1 9 6 2 7 9 7 5 2 9 7 0 0 1 4 6 4 0 0 2 7 6 7 2 9 2 3 3 7 1 8 8 4 6 9 4 1 8 0 1 8 4 3
1 5 7 7 1 6 0 4 0 5 6 9 7 1 6 2 6 3 1 2 9 5 2 2 2 0 6 9 5 4 8 5 4 3 7 4 8 8 8 1 2 1 9 4 8 6 1 6 8 0 3 3 8 6 4 4 2 5 8 3 8 8 4 9 6 0 8 9 4 6 6 4 6 8 8 0 0 0 5 2 2 5 8 8 8 0 9 8 3 6 6 8 4 2 3 2 7 3 3 7
7 4 8 7 4 3 4 6 4 8 0 6 8 7 7 1 5 8 3 7 6 0 6 7 5 7 3 5 3 0 1 5 5 8 0 3 0 1 6 5 9 0 8 9 7 7 8 1 9 9 8 4 3 6 3 3 6 4 0 2 1 3 1 9 0 8 8 3 2 1 3 2 3 9 2 6 0 0 4 1 7 5 4 4 1 7 9 4 1 6 8 2 6 0 2 1 1 1 8 4
1 9 8 6 5 9 6 0 3 7 4 8 0 6 7 1 0 0 9 9 5 9 3 9 0 2 7 1 3 9 8 7 6 9 4 7 5 2 1 4 4 9 9 9 4 4 2 6 1 5 4 9 7 1 1 1 8 2 5 5 6 1 4 5 4 8 8 8 5 1 9 2 6 2 1 8 5 0 0 8 9 8 9 6 4 0 5 5 8 9 7 8 4 9 6 6 5 5 3 5
6 9 1 9 0 0 0 4 2 4 9 0 2 8 7 6 1 5 3 6 5 5 9 6 0 7 6 7 3 7 5 8 7 3 5 8 6 1 1 5 7 0 2 5 2 0 3 1 1 5 0 6 4 7 6 1 3 2 7 3 5 1 9 8 7 6 0 2 5 6 7 7 6 5 2 1 0 9 0 0 0 7 1 0 9 2 6 3 1 8 9 3 7 9 1 9 7 3 1 8
2 8 3 3 8 5 9 5 1 0 9 7 4 7 2 7 1 4 0 3 6 3 1 2 2 5 2 0 4 3 4 0 3 2 4 9 0 6 0 8 5 9 3 9 7 1 1 0 0 4 0 5 2 7 2 6 1 2 6 8 4 6 8 7 0 7 6 8 2 7 9 4 9 1 7 7 9 9 8 0 0 1 9 8 8 9 8 8 0 0 0 6 6 4 2 9 8 1 5 9
2 6 4 5 8 7 0 1 2 4 8 0 1 8 2 3 7 5 0 1 8 9 7 7 0 2 4 8 8 1 2 4 3 9 4 6 2 5 3 9 4 0 2 0 5 9 8 9 1 3 3 2 1 3 6 9 6 0 4 0 8 5 0 1 3 3 9 5 5 3 1 6 0 7 7 1 0 6 6 3 0 0 1 2 6 7 6 1 8 1 6 3 8 2 4 7 2 8 2 3
6 2 6 8 6 2 0 6 3 1 9 7 1 6 0 9 5 2 4 5 1 1 6 6 3 1 6 8 3 8 3 9 0 8 1 7 0 7 3 6 1 3 4 8 3 9 2 8 1 7 3 1 6 8 9 1 4 2 9 2 1 7 2 6 7 5 2 5 3 2 6 4 6 4 8 8 8 4 3 2 3 0 0 5 3 7 6 7 6 7 7 1 2 3 5 8 6 7 0 8
9 4 7 8 8 2 4 9 0 7 1 8 1 4 4 5 9 8 9 9 1 0 5 5 8 7 0 2 8 8 3 5 6 5 1 5 7 0 9 8 7 8 4 5 2 2 2 8 8 7 1 9 1 3 1 4 0 4 1 1 9 6 4 8 5 5 7 8 5 7 8 5 6 4 0 3 6 8 3 6 6 0 0 0 7 9 2 3 7 6 9 4 3 1 8 9 5 7 7 8
4 2 2 3 4 3 7 5 5 9 7 3 8 7 1 2 6 5 1 8 3 5 2 0 5 3 4 4 5 7 8 0 1 9 6 5 1 3 8 1 2 2 3 5 8 9 6 4 3 2 9 1 6 9 7 1 2 8 5 9 6 9 8 7 9 3 0 5 3 0 4 5 0 5 1 4 3 1 4 8 0 2 7 0 0 7 2 4 6 1 4 6 6 9 7 1 6 9 3 9
9 1 3 9 0 1 4 5 5 7 3 2 5 4 4 5 8 7 5 5 8 3 8 2 9 2 7 7 6 1 3 2 5 2 4 1 0 9 6 6 2 1 7 3 2 9 1 3 3 3 5 2 8 0 2 1 5 6 6 8 6 6 9 4 7 5 3 8 4 4 0 9 3 5 6 3 2 1 9 8 1 8 4 3 0 0 9 9 0 3 7 0 1 9 9 1 6 9 5 2
8 6 4 6 3 9 0 6 9 1 5 6 0 0 3 4 8 8 8 4 5 2 4 5 8 9 2 7 5 2 6 0 0 4 7 1 2 2 9 9 7 8 7 5 4 5 9 6 3 0 0 2 4 3 4 4 7 6 7 6 6 4 9 1 8 7 7 9 2 6 1 5 0 9 0 5 2 9 8 7 0 8 3 0 4 0 0 9 8 0 7 0 7 0 0 7 3 1 1 0
4 5 4 8 3 0 8 8 3 5 8 6 0 7 8 8 5 0 8 1 2 2 9 9 1 6 9 5 9 3 8 5 8 6 6 2 8 1 6 7 9 5 9 0 0 9 3 4 9 3 9 9 8 2 2 2 6 2 0 5 7 9 7 7 7 1 1 1 8 0 8 2 3 1 7 2 2 8 9 6 9 3 9 5 8 0 0 0 5 9 5 7 8 4 7 3 5 1 1 6
7 0 1 5 3 0 8 0 1 6 6 6 5 9 8 8 0 4 5 6 7 7 4 9 4 5 2 3 8 8 8 0 6 1 1 2 1 0 8 1 3 8 9 1 2 7 8 2 3 1 1 4 0 2 7 5 1 9 4 2 5 4 8 7 2 5 7 9 0 3 9 5 1 2 3 3 6 7 5 5 8 6 6 5 8 7 4 0 0 7 8 8 9 6 6 1 1 5 7 5
0 8 1 2 8 8 1 2 3 1 4 0 2 6 5 4 9 4 4 6 6 9 2 6 2 9 2 3 8 2 6 6 6 3 5 0 4 1 3 4 6 0 5 6 7 5 0 9 0 5 5 6 8 9 0 3 0 2 9 5 7 1 7 2 6 4 6 0 5 3 3 1 0 1 9 5 5 2 4 2 7 1 2 3 2 0 5 3 0 0 4 9 4 1 9 3 6 2 0 6
8 0 0 0 5 5 5 6 1 2 5 7 6 5 3 4 6 0 9 3 2 4 1 1 4 0 9 9 3 5 2 0 4 0 7 1 3 2 7 8 2 3 2 9 1 6 6 4 5 5 7 0 0 1 1 0 0 8 6 9 0 5 2 5 9 0 9 4 1 4 4 0 3 8 5 6 4 9 8 1 2 9 5 6 9 1 1 2 1 0 0 1 5 3 9 4 0 3 1 9
3 9 9 5 2 4 1 5 3 3 1 0 7 7 0 7 2 0 9 6 7 1 1 1 6 9 5 3 4 4 3 6 6 2 4 8 5 7 7 0 5 3 8 4 8 0 2 3 7 3 5 9 8 2 7 1 8 1 9 6 5 7 1 7 9 4 9 5 0 6 0 7 8 2 2 0 5 9 6 4 8 2 3 6 6 4 3 7 3 4 0 0 3 1 0 4 3 8 2 7
6 0 9 5 6 2 9 9 6 4 5 7 6 6 1 5 1 9 0 8 4 8 1 5 3 7 8 0 3 9 1 1 8 2 3 8 4 1 3 7 9 0 4 8 1 1 5 9 1 4 2 6 1 7 5 1 0 3 0 5 2 2 9 6 5 0 5 0 4 1 0 1 9 8 8 3 9 5 3 0 5 6 4 5 4 9 5 1 2 2 6 0 0 2 1 9 0 1 6 9
4 0 0 4 9 4 4 4 8 5 4 2 7 5 8 7 2 5 3 3 8 9 3 1 3 8 9 6 5 2 3 9 7 5 5 1 5 7 9 4 0 3 3 3 2 2 1 8 5 7 3 2 9 4 7 8 3 3 6 8 6 1 7 0 4 7 7 9 7 6 5 1 4 5 8 9 9 5 8 0 8 9 3 2 9 6 3 8 1 9 5 4 0 0 7 2 7 9 4 3
8 3 2 0 9 1 0 1 6 1 6 8 0 4 5 6 0 8 4 2 2 0 2 3 7 8 6 2 2 9 4 4 1 5 1 2 0 3 5 3 0 7 7 6 9 0 5 7 9 0 1 0 6 9 0 2 9 7 5 4 0 9 2 8 3 3 0 8 4 0 8 6 1 3 9 0 7 7 0 5 3 7 7 5 9 6 3 0 6 5 8 8 2 0 0 7 0 1 5 7
5 5 7 5 3 7 7 0 8 6 8 1 2 8 3 5 0 6 9 3 0 7 4 2 8 2 3 3 0 8 7 9 5 8 1 7 2 9 2 4 7 3 0 8 7 7 6 3 2 3 6 8 1 2 3 0 6 9 9 3 8 7 6 7 7 1 4 1 0 1 4 5 7 8 0 9 8 1 9 4 7 3 7 2 9 8 3 5 5 3 1 3 1 4 0 0 9 4 2 9
7 7 9 3 4 0 9 5 6 3 3 2 1 7 6 7 8 6 5 3 1 6 9 4 5 0 7 5 3 7 9 6 6 8 4 0 6 5 3 1 8 5 7 1 1 2 0 9 6 4 5 4 4 4 3 5 1 0 5 7 0 1 9 1 0 0 6 2 4 1 7 4 6 2 6 6 3 3 7 5 6 5 1 4 3 3 4 9 7 7 3 2 8 0 8 0 0 1 4 3
8 6 0 0 0 5 8 3 1 5 7 3 2 0 2 3 7 1 2 9 3 9 5 2 1 8 0 5 7 4 4 9 4 5 0 8 7 1 3 0 0 1 9 6 5 1 5 4 4 7 4 2 9 1 6 1 3 8 3 5 6 4 5 9 1 9 5 5 0 2 2 1 7 8 3 5 0 5 1 7 8 4 2 4 3 0 1 5 6 6 1 4 2 7 7 3 0 0 1 3
3 9 5 6 6 5 0 2 3 5 5 6 8 8 0 2 5 6 0 8 8 3 6 7 7 8 5 1 9 7 2 3 1 1 7 1 7 3 8 0 5 8 4 5 2 1 0 7 2 2 3 1 0 3 9 1 0 8 5 5 8 4 0 1 0 6 9 4 3 0 9 3 8 2 9 8 4 5 4 3 9 6 5 5 4 4 8 9 0 6 4 9 2 1 7 7 5 0 0 6
2 8 1 3 5 6 6 4 5 8 9 7 5 3 7 0 0 2 2 5 7 6 5 8 3 4 8 8 9 5 3 7 4 9 9 3 7 1 5 3 2 3 9 1 2 3 2 5 6 5 1 4 9 1 3 2 6 1 0 3 8 8 4 5 0 0 9 0 7 9 9 5 7 6 7 1 0 6 6 9 9 4 6 3 4 8 8 3 9 2 1 2 6 1 0 0 7 8 0 0
4 3 6 2 4 3 9 2 6 6 2 0 6 4 9 1 2 3 4 1 0 3 4 0 6 5 1 8 3 8 9 4 2 6 0 4 2 9 9 9 1 4 8 3 9 1 9 7 7 5 9 8 0 3 0 6 5 8 8 0 2 2 2 5 5 0 4 3 9 4 0 6 3 3 7 9 9 3 7 6 4 1 5 1 2 5 7 3 3 5 8 4 9 4 0 8 1 8 6 0
0

예제 출력 A

Problem 1: 110
Problem 2: 229
Problem 3: 0

출처

ICPC > Regionals > North America > Pacific Northwest Regional > 2008 Pacific Northwest Region Programming Contest D번

• 문제를 번역한 사람: kks227

알고리즘 분류

• 그래프 이론
• 데이크스트라

---

---

이 문제는 [0, 0]에서 [n-1, n-1]까지 이동할 때, 가장 적게 잃을 수 있는 금액이 얼마인지에 대하여 구하는 문제입니다.

도둑 루피의 크기를 노드 사이의 비용으로 생각하면 최소비용을 구하는 문제와 같습니다.

map[MAXN][MAXN] 2차원 배열에 [i][j]로 이동하는 비용을 저장하고

dis[MAXN][MAXN] 2차원 배열에 Dijkstra 알고리즘으로 [i][j]의 최소 비용을 업데이트하여 문제를 해결하였습니다.

또한 우선순위 큐를 사용하여 최솟값 노드를 선택하는 방법을 사용했습니다.

통과된 코드

#include <iostream>
#include <queue>
#include <tuple>

using namespace std;

constexpr int MAXN = 125;
constexpr int INF = INT32_MAX;

// 탐색하는 방향 설정 =>  상, 하 ,좌 ,우
int dxdy[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };

int N, nowX, nowY, dcost;

int map[MAXN][MAXN], dis[MAXN][MAXN];

tuple<int, int, int> nowTuple;

// 가중치, x,y 좌표
priority_queue<tuple<int, int, int>> myPQ;

queue<int> resQ;


int main()
{
	ios_base::sync_with_stdio(false); // scanf와 동기화를 비활성화
	// cin.tie(null); 코드는 cin과 cout의 묶음을 풀어줍니다.
	cin.tie(NULL);
	cout.tie(NULL);

	while (true) {
		cin >> N; // 테스트 케이스가 0이면 break;
		if (N == 0) break;

		// 2차원 배열 초기화
		// 전체 초기화 : 처음에는 [0][0]을 써주고, 
		// 그 다음 칸에는 [최대 행(값) - 1][최대 열], 다음 칸에는 초기 상태의 값
		// 범위내의 임시 노드를 무한대 변경
		fill(&dis[0][0], &dis[N - 1][N], INF);

		// 테스트 케이스의 입력을 받는다.
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				cin >> map[i][j];
			}
		}

		// 우선순위 큐를 이용하기 위하여 음수를 넣는 것을 기억하자
		myPQ.push(make_tuple(-map[0][0], 0, 0));

		while (!myPQ.empty()){

			// 0번 인덱스 가중치, 1번 인덱스 X좌표, 2번 인덱스 Y좌표
			nowTuple = myPQ.top();
			myPQ.pop();

			if (get<1>(nowTuple) == N - 1 && get<1>(nowTuple) == N - 2) break;

			// 상/하/좌/우를 탐색하기 위한 반복문
			for (int i = 0; i < 4; i++) {
				nowX = get<1>(nowTuple) + dxdy[i][0];
				nowY = get<2>(nowTuple) + dxdy[i][1];
				dcost = get<0>(nowTuple) * -1;

				// 문제의 범위를 벗어나는 경우 => 넘어간다.
				if (nowX < 0 || nowY < 0 || nowX >= N || nowY >= N) continue;
				// 현재 위치의 최소 도둑루피 + 다음 칸의 도둑루피의 크기 >= 탐색 위치의 최소 도둑루피
				if (dcost + map[nowX][nowY] >= dis[nowX][nowY]) continue;
				else {
					// 임시 노드 업데이트
					dis[nowX][nowY] = dcost + map[nowX][nowY];
					myPQ.push(make_tuple( -dis[nowX][nowY], nowX, nowY));
				}
			}
		}

		resQ.push(dis[N - 1][N - 1]);
	}

	int cnt = 1;
	while (!resQ.empty()){
		cout << "Problem " << cnt << ": " << resQ.front() << "\n";
		resQ.pop();
		cnt++;
	}

	return 0;
}

Priority_Queue 에 음수로 넣는 것을 깜빡해서 시간 초과가 발생하였다.