20158번 - 사장님 달려가고 있습니다

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

• 공사 지도 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이라면 통제를 하지 않는다.

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

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