센서

한 고속도로 위에 N개의 센서가 설치되어 있다. 이 센서들이 모은 자료를 수집하고 분석하기 위해, 예산 범위 안에서 최대 K개의 집중국을 고속도로 위에 세울 수 있다.

각 집중국은 자신이 수신할 수 있는 구간을 조절할 수 있다. 수신 가능 영역은 고속도로 위의 하나의 연결된 구간으로 나타난다. 모든 센서는 적어도 하나의 집중국과 통신할 수 있어야 한다. 또한 유지비를 줄이기 위해, 설치한 집중국들의 수신 가능 영역 길이의 합을 최소로 만들어야 한다.

고속도로는 평면 위의 직선이라고 가정한다. 각 센서는 이 직선 위의 기준점인 원점으로부터 떨어진 정수 거리 위치에 놓여 있으며, 따라서 센서의 위치는 정수 하나로 표현된다. 모든 센서의 좌표가 서로 다를 필요는 없다. 최대 K개의 집중국을 사용할 때, 모든 센서를 덮는 수신 가능 영역 길이 합의 최솟값을 구하라. 각 집중국의 수신 가능 영역 길이는 0 이상이다.

첫째 줄에 센서의 개수 N (1 <= N <= 10,000)이 주어진다.

둘째 줄에 집중국의 최대 개수 K (1 <= K <= 1,000)가 주어진다.

셋째 줄에는 센서의 좌표 N개가 공백으로 구분되어 주어진다. 각 좌표는 정수이며, 절댓값은 1,000,000 이하이다.

최대 K개의 집중국을 사용할 때, 모든 센서를 통신 가능하게 하는 수신 가능 영역 길이 합의 최솟값을 출력한다.