징검다리 달리기 2

징검다리는 원래 개울을 건너기 위해 놓였지만, 놀이를 좋아하는 사람들은 이 징검다리 위에서 달리기 경기를 하기로 했다.

각 징검다리의 위치는 좌표쌍 (x, y)로 표현된다. 시작점은 항상 원점 (0, 0)이다. 경기 중에는 현재 있는 징검다리에서 x좌표 차이가 2 이하이고 y좌표 차이도 2 이하인 징검다리로만 점프할 수 있다. 결승선은 x축에 평행한 직선이다. 결승선과 같은 y좌표를 가진 징검다리에 도착하면 결승선을 통과한 것으로 보고 경기가 끝난다.

징검다리들의 위치가 주어졌을 때, 경기를 끝내는 가장 빠른 경로를 구하라. 가장 빠른 경로란 그 경로를 이루는 점프 길이의 합이 최소인 경로를 뜻한다. (x1, y1)에 있는 징검다리에서 (x2, y2)에 있는 징검다리로 점프할 때의 길이는 sqrt((x1 - x2)^2 + (y1 - y2)^2)로 정의한다.

첫째 줄에 징검다리의 개수 N과 결승선의 y좌표 F가 주어진다.

둘째 줄부터 N개의 줄에는 각 징검다리의 좌표가 한 줄에 하나씩 주어진다.

N은 50,000 이하의 자연수이다. F와 모든 좌표는 0 이상 1,000,000 이하의 정수이다. y좌표가 F를 초과하는 징검다리는 입력되지 않는다. (0, 0)은 입력되는 N개의 징검다리에 포함되지 않지만, 시작점이라는 점에 유의하라.

가장 빠른 경로의 길이를 소수 첫째 자리에서 반올림한 정수로 출력한다. 도달할 수 없다면 -1을 출력한다.

(0,0) - (1,2) - (3,2) - (4,1) - (6,3) 경로를 따라가면 전체 길이는 8.4787...이고, 이 경로가 최단 경로이다.