경비행기

경비행기 독수리호는 출발지 S에서 목적지 T까지 가능한 빠르게 이동하려고 한다. 연료통이 크면 중간에 착륙해 급유하는 횟수를 줄일 수 있지만, 무게 때문에 속도와 안정성에 문제가 생길 수 있다. 반대로 연료통이 작으면 비행은 빨라지지만 더 자주 급유해야 한다.

최대 k번 이하로 중간 급유지에 착륙할 수 있을 때, S에서 T까지 이동하는 데 필요한 연료통의 최소 용량을 구하라.

그림과 같은 상황에서 허용되는 중간 착륙 횟수가 k = 2라면, 어떤 경로는 마지막 구간이 매우 길어 큰 연료통이 필요할 수 있다. 목표는 허용된 중간 착륙 횟수 안에서 각 비행 구간의 필요 연료량 중 최댓값을 최소화하는 것이다.

다음 조건을 따른다.

1. 모든 비행기는 두 지점 사이를 직선으로만 이동한다. 거리 단위는 km이고 연료 단위는 L이다. 연료 1L로 10km를 비행할 수 있으며, 연료는 정수 L 단위로 주입한다.
2. 두 위치 사이의 거리는 평면상의 유클리드 거리이다. 예를 들어 g = (2, 1), h = (37, 43)이면 거리 d(g, h)는 \(\sqrt{(2-37)^2 + (1-43)^2}\) = 54.671... 이다. 따라서 50 < d(g, h) <= 60이므로 이 구간에는 6L가 필요하다.
3. 출발지 S의 좌표는 항상 (0, 0), 목적지 T의 좌표는 항상 (10000, 10000)이다.
4. 출발지와 목적지를 제외한 비행장의 수 n은 3 <= n <= 1000이다. 각 비행장 좌표 (x, y)는 0 < x, y < 10000인 정수이다. 최대 허용 중간 급유 횟수 k는 0 <= k <= 1000이다.

첫째 줄에 비행장의 수 n과 최대 허용 중간 급유 횟수 k가 공백으로 구분되어 주어진다.

다음 n개의 줄에는 각 비행장(급유지)의 정수 좌표 x y가 한 줄에 하나씩 주어진다.

S에서 T까지 중간 급유를 k번 이하로 하며 이동할 수 있도록 하는 연료통의 최소 용량을 정수로 출력한다.