같은 칸에 담을 소포

문제

한 우체국에서는 도착한 소포 중 일부를 골라 운반차의 같은 칸에 싣는다. 소포마다 무게가 다르므로, 같은 칸에 실린 소포들의 무게 차이가 작을수록 칸 내부의 고정 장치를 조절하기 쉽다. 담당자는 오늘 도착한 N개의 소포 중 정확히 K개를 골라 하나의 칸에 싣기로 했다. 칸의 조절 폭은 선택한 소포 중 가장 무거운 소포의 무게에서 가장 가벼운 소포의 무게를 뺀 값이다. 예를 들어 선택한 소포의 무게가 8, 11, 9라면 조절 폭은 3이다. 선택한 소포의 무게가 모두 같으면 조절 폭은 0이다. 소포를 하나만 고르는 경우에도 가장 무거운 소포와 가장 가벼운 소포가 같은 소포이므로 조절 폭은 0이다. 소포는 도착한 순서와 관계없이 고를 수 있다. 입력에서 이웃한 소포끼리만 골라야 한다는 제한은 없으며, 고르지 않은 소포는 다른 운반차를 위해 남겨 둔다. 각 소포는 하나의 물건이므로 같은 소포를 두 번 고를 수 없다. 무게가 같은 소포가 여러 개 있더라도 서로 다른 소포이며, 필요한 개수만큼 각각 선택할 수 있다. 담당자는 조절 폭이 가능한 한 작아지도록 소포를 고르려고 한다. 선택한 소포의 무게를 바꾸거나 여러 소포를 하나로 합치는 작업은 허용하지 않는다. 또한 소포를 고르는 방법 자체를 출력할 필요는 없다. 최소 조절 폭을 만드는 선택이 여러 가지라면 어느 선택을 사용해도 결과는 같으므로, 그 조절 폭만 구한다. 항상 K가 N 이하인 입력이 주어지므로 소포를 고를 수 없는 경우는 없다. 주어진 소포들의 무게를 이용하여 가능한 최소 조절 폭을 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N과 K가 주어진다. 1 ≤ K ≤ N ≤ 40,000이다.
둘째 줄에 각 소포의 무게를 나타내는 정수 N개가 공백으로 구분되어 주어진다. 각 무게는 1 이상 999,999 이하이다.

출력

정확히 K개의 소포를 골랐을 때 가능한 최소 조절 폭을 정수 하나로 출력한다.

7 3
14 6 20 9 8 30 15

3

5 4
12 12 12 12 19

0

1 1
999999

0

출처: Devin.KR 자체 제작