공유기 설치

1차원 직선 위에 N개의 집이 있다. C개의 공유기를 집에 하나씩 설치할 때, 인접한 두 공유기 사이의 최소 거리를 최대화하라. 최소 간격 d를 이분 탐색하여, 간격이 d 이상이 되도록 공유기를 탐욕적으로 배치할 때 C개 이상 설치 가능한지 판단한다. ## 입력 첫째 줄에 N과 C가 공백으로 구분되어 주어진다. (2 ≤ C ≤ N ≤ 200,000) 둘째 줄부터 N개의 줄에 각 집의 좌표가 주어진다. (0 ≤ 좌표 ≤ 10^9) ## 출력 인접한 공유기 사이의 최소 거리의 최댓값을 출력하라. ## 예제 입력 1 ``` 5 3 1 2 8 4 9 ``` ## 예제 출력 1 ``` 3 ```