행복 유치원

행복 유치원 원장 태양이는 원생 N명을 키 순서대로 한 줄로 세운 뒤, 이 줄을 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하고, 같은 조에 속한 원생은 줄에서 서로 이웃해야 한다. 조마다 인원수가 같을 필요는 없다.

각 조는 단체 티셔츠를 맞춘다. 한 조의 비용은 그 조에서 키가 가장 큰 원생과 가장 작은 원생의 키 차이다. K개 조의 비용을 모두 더한 값이 최소가 되도록 나눌 때, 그 최소 합을 구하여라.

첫째 줄에 원생 수 N($1 \le N \le 300{,}000$)과 조의 개수 K($1 \le K \le N$)가 공백으로 구분되어 주어진다.

둘째 줄에 원생 N명의 키가 줄을 선 순서대로 공백으로 구분되어 주어진다. 태양이가 키 순서대로 세웠으므로 왼쪽 원생의 키는 오른쪽 원생의 키보다 크지 않다. 키는 $10^9$ 이하의 자연수이다.

비용의 합이 최소가 되도록 K개의 조로 나누었을 때, 그 최소 비용을 출력한다.

N = 5, K = 3이고 키가 1, 3, 5, 6, 10인 경우, (1, 3), (5, 6), (10)으로 나누면 비용이 2 + 1 + 0 = 3이 되어 최소다.