Guard Duty (중간)

Princess Heidi는 자신의 모든 K Rebel 함선 지휘관에게 직접 명령을 내리기로 했다. 불행히도 그녀는 현재 초공간을 통과하고 있으며, N개의 특정 시각 t1, t2, ..., tN에만 초공간을 벗어난다. 따라서 지휘관들과의 회의는 반드시 그 시각들에 시작하고 끝나야 한다. 즉, 각 지휘관은 어떤 시각 ti에 그녀의 함선에 승선하고, 그보다 나중 시각 tj에 하선한다. 물론 Heidi는 모든 지휘관과 만나야 하며, 같은 시간에 두 회의를 진행할 수 없다. 초공간 도약의 시작/종료 시점에는 두 지휘관이 마주치는 것조차 허용되지 않는다. 한 위치에 함선이 너무 많으면 적에게 그들의 좌표가 노출될 수 있기 때문이다.

위 조건을 만족하는 일정에서 Princess Heidi가 회의에 써야 하는 최소 시간을 구한다.

첫 줄에 두 정수 K, N (2 ≤ 2K ≤ N ≤ 500000, K ≤ 5000)가 주어진다. 둘째 줄에는 Heidi가 초공간을 벗어나는 시각을 나타내는 서로 다른 정수 N개 t1, t2, ..., tN (1 ≤ ti ≤ 109)가 주어진다.

회의에 사용한 최소 시간을 나타내는 정수 하나만 출력한다.

첫 번째 예제에는 유효한 일정이 다섯 가지 있다. $[1, 4]$, $[6, 7]$는 총 시간이 4이고, $[1, 4]$, $[6, 12]$는 총 시간이 9이며, $[1, 4]$, $[7, 12]$는 총 시간이 8이고, $[1, 6]$, $[7, 12]$는 총 시간이 10이며, $[4, 6]$, $[7, 12]$는 총 시간이 7이다. 따라서 답은 4이다.

두 번째 예제에는 유효한 일정이 오직 1개뿐이다: $[1, 2]$, $[3, 4]$, $[5, 6]$.

세 번째 예제에서 총 시간이 6인 가능한 일정 하나는 다음과 같다: $[1, 3]$, $[4, 5]$, $[14, 15]$, $[23, 25]$.