====== 난로 ======

===== 풀이 =====
  * 꺼져있는 시간을 최대로 하면, 켜져있는 시간은 최소가 된다. 켜져있는 K개의 구간을 찾는것보다 꺼져있는 K-1개의 구간을 찾는 것이 더 쉽다. 
  * 꺼져있는 구간은, 첫번째 친구가 온 시점부터 마지막 친구가 가는 시점 사이에 총 K-1번이 있을 수 있다. 꺼져있는 구간이 될 수 있는 후보들은, i번째 친구가 나가는 시점부터 i+1번 친구가 들어오는 시점이므로, 총 N-1개의 구간이다. 이 N-1개의 구간중 가장 긴 구간 K-1개를 찾아서 그 시간동안 촛불을 꺼두면 된다. 
  * 시간복잡도는 O(n)개의 원소중에서 최솟값 O(k)개를 찾는데 걸리는 시간이므로 우선순위큐를 써서 O(n+klogn)에 찾을수 있다. 하지만, k가 최대 n이므로, 결국 O(nlogn)이고, 그러면 다 정렬해놓고 k개를 찾는 방법이 더 빠르게 동작한다. 

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 15553. 난로".

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

Tags: [greedy]
"""

import itertools
import sys


def main():
    N, K = [int(x) for x in sys.stdin.readline().split()]
    T = [int(sys.stdin.readline()) for _ in range(N)]

    no_visitor_times = sorted(
        (y - x - 1 for x, y in itertools.pairwise(T)), reverse=True
    )
    answer = T[-1] - T[0] + 1 - sum(no_visitor_times[: K - 1])

    print(answer)


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

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