시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 1024 MB 236 19 13 11.607%

문제

알바 첫날인 정훈이는 늦잠을 잤다. 다행히도 정훈이는 달리기가 정말 빨라서 괜찮다고 생각했지만, 오늘은 공사로 인해 길을 통제하는 중이었다. 첫날부터 늦을 수 없는 정훈이는 가장 빠른 경로를 생각하며 달린다.

  • 공사 지도 N x N가 있다.
  • 정훈이는 0초에 맨 왼쪽 위(1, 1)에서 출발하고 맨 오른쪽 아래(N, N)에 도착해야 한다.
  • 달리는 방향은 상,하,좌,우로 달릴 수 있다.
  • 매초 1칸을 갈 수 있고 전과 같은 방향으로 달린다면 가속도가 붙어 1초 안에 전보다 1칸을 더 갈 수 있다. (전에 오른쪽으로 1칸을 갔다면 오른쪽으로 2칸을 1초에 갈 수 있다.)
  • 가속도를 주체할 수 없으므로 방향전환을 해야만 다시 1초에 1칸을 갈 수 있다.
  • 정훈이는 현재 위치에서 달려갈 때 1초 후 지도 밖에 서 있다면 갈 수 없다고 판단한다.

공사로 인해 통제하는 구역은 N x N 지도에 통제 시작시각이 초 단위로 주어지며 통제를 시작하기 전까지만 그 구역을 들어갈 수 있다. 통제 시작시각과 그 구역에 도착시각이 같은 시간일 경우에는 구역에 들어갈 수 없다.

입력

정수 N (1 ≤ N ≤ 100)이 주어진다.

둘째 줄부터 N개의 줄에 공사 지도의 정보가 주어진다. 지도에는 각 구역 통제 시작 시각 X (0 ≤ X ≤ 100)이 정수로 주어진다. X가 0이라면 통제를 하지 않는다.

출력

정훈이가 (NN)에 도착할 수 있는 최소 시간을 출력한다.

(NN)에 도착할 수 없다면 "Fired"를 출력한다.

예제 입력 1

5
0 0 0 2 0
0 1 0 0 0
0 0 0 3 0
5 0 0 0 0
0 0 6 0 0

예제 출력 1

6

예제 입력 2

2
0 1
1 1

예제 출력 2

Fired

예제 입력 3

4
0 0 2 0
1 1 1 0
1 1 1 0
1 1 1 0

예제 출력 3

4