시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 15 1 1 100.000%

문제

다해는 평소 산악자전거 타기를 즐긴다. 다해는 오랜 시간동안 운동을 하는 것도 좋아하지만, 때로는 되도록 짧은 시간동안 산악자전거 타기를 마치기를 원하기도 한다.

산의 모습은 R(1≤R≤100)행 C(1≤C≤100)열의 행렬로 표현된다. 행렬의 각 수는 그 위치의 높이(고도)를 나타낸다. 다해는 현재 행렬의 (1, 1) 위치에 있고, (R, C) 위치로 이동하려 한다. 다해의 (1, 1)위치에서의 초기 속도는 V(1≤V≤1,000,000)이다. 행렬에서의 움직임은 위, 아래, 왼쪽, 오른쪽의 네 방향으로만 가능하다고 하자. 속도가 V라는 의미는 단위시간동안 V칸을 움직일 수 있다는 의미이다.

자전거를 타고 이동하다보면 높이 차이에 의해 속도가 가속되기도 하고 감속되기도 한다. 현재 위치의 높이가 A이고, 이동하려는 위치의 높이가 B일 때, 속도는 배가 된다(2^(A-B) 배). 실제로는 이동하는 도중에 속도가 변하게 되지만, 문제의 편의를 위해서 이동을 완전히 마친 후에 속도가 변하는 것으로 생각하자. 즉, 이동을 할 때에는 처음의 속도를 가지고 이동하는 것으로 한다.

산의 높이에 대한 정보와 초기 속도가 주어졌을 때, (1, 1)의 위치에서 (R, C)의 위치로 이동할 때 필요한 최소 시간을 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 세 정수 V, R, C가 주어진다. 다음 R개의 줄에는 C개의 정수로 행렬이 주어진다. 행렬의 각 수는 -25이상 25이하의 정수이다.

출력

첫째 줄에 이동에 필요한 최소 시간을 출력한다. 답을 출력할 때에는 소수점 아래 둘째 자리까지 출력한다(셋째 자리에서 반올림).

예제 입력

1 2 3
2 1 2
9 9 1

예제 출력

2.50

힌트