====== 행복 유치원 ======

===== 풀이 =====
  * K개의 조를 a[0]~a[i1] / a[i1+1]~a[i2] / a[i2+1]~a[i3] / ... / a[i(k-1)+1] ~ a[n-1] 으로 나눠서 만들었다고 하면. 티셔츠의 비용은 a[i1]-a[0] + a[i2]-a[i1+1] + ... + a[n-1] - a[i(k-1)+1] 이다. 식 순서를 바꾸면 (a[n-1]-a[0]) - (a[i1+1] - a[i1]) - (a[i2+1] - a[i2]) - ... - (a[i(k-1)+1] - a[i(k-1)]) 이 된다. 즉 고정된 값에서, 인접한 숫자 페어를 (k-1)개 골라서 그 차를 전부 빼준것이고, 이 값이 최소가 되게 하려면 빼주는 값을 최대로 하면 된다. 결국 인접한 숫자 페어중 차이가 가장 큰 것을 k-1개 찾아서 빼면 된다.
  * 식을 조금 바꿔서 a[n-1]-a[0] = (a[1]-a[0]) + (a[2]-a[1]) + ... + (a[n-1]-a[n-2])로 바꿔서 쓰면, 인접한 숫자 페어의 차 중에서 가장 작은값 n-k개를 더해주는 것으로 바꿀수도 있다.
  * 인접한 숫자간의 차이들을 O(n)에 구하고, O(nlogn)에 정렬한 뒤에 (n-k)개의 합을 구하면 되므로 총 시간복잡도는 O(nlogn).
  * [[ps:problems:boj:2212]]도, 문제 설명은 좀 다르지만, 결국 동일한 것을 구하는 문제이다

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 13164. 행복 유치원".

- Problem link: https://www.acmicpc.net/problem/13164
- Solution link: http://www.teferi.net/ps/problems/boj/13164

Tags: [Greedy]
"""

import itertools


def main():
    N, K = [int(x) for x in input().split()]  # pylint: disable=unused-variable
    heights = [int(x) for x in input().split()]

    diffs = [b - a for a, b in itertools.pairwise(heights)]
    print(sum(sorted(diffs)[:N - K]))


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:골드_5}}