4557 - EXIT

Time Limit: 1s Memory Limit: 128MB

Submissions: 254 Solved: 52
Description

도시에 유독가스가 퍼지기 시작하였다.

용남이는 유독가스를 피해 건물 옥상을 통해 구조헬기 쪽으로 도망가려고 한다. 다행히 용남이에게는 클라이밍용 장비들이 있어서 최대 a만큼 높거나 낮은 건물로 이동할 수 있다.

유독가스는 시간당 1씩 위로 올라오며, 유독가스가 용남이가 있는 건물보다 높아지는 경우 용남이는 죽는다.

용남이는 상하좌우 방향으로 인접한 건물로 시간당 한 번 이동할 수 있다.

용남이는 지도의 맨 왼쪽 위에 있고, 구조헬기는 지도의 맨 오른쪽 아래에 있다.

용남이가 구조헬기까지 최단시간에 이동하려고 할 때, 얼마나 걸리게 될 지 계산해보자.

Input

* Line 1: 이동가능한 최대 높낮이 a (1 ≤ a ≤ 10)

* Line 2: 지도의 가로길이 n, 세로길이 m (1 ≤ n,m ≤ 10)

* Line 3~m+2: 건물 옥상의 높이를 표시한 지도

Output

* Line 1: 지도의 맨 왼쪽 위에 있는 용남이가 지도의 맨 오른쪽 아래의 구조헬기에 도착하는데 걸리는 최소시간을 출력하고, 도달할 수 없다면 IMPOSSIBLE 출력

Sample Input
2
4 5
0 2 4 3
8 8 7 5
9 10 11 12
10 15 14 13
12 14 16 18
Sample Output
13
Hint

0 → 2 → 4 → 3

                      ↓

8     8 ← 7 ← 5

        ↓

9    10 → 11 → 12

                           ↓

10    15    14 ← 13

                  ↓

12    14    16 → 18

 

또는

0 → 2 → 4 → 3

                      ↓

8 ← 8 ← 7 ← 5

9    10    11    12

10    15    14    13

12 → 14 → 16 → 18