문제
조이의 집에는 난로가 하나 있다.
조이는 추위에 강하기 때문에 집에 혼자 있을 때는 난로를 켜지 않아도 되지만, 손님이 오면 난로를 켜야 한다.
오늘, 조이의 집에는 N명의 손님이 온다.
i번째 (1 ≦ i ≦ N) 손님은 시간 T_i에 와서 시간 T_i + 1에 나간다.
같은 시간에 2명 이상의 손님이 조이의 집에 있는 경우는 없다.
조이는 임의의 시간에 난로를 껐다 켰다 할 수 있다.
그러나 난로를 켤 때마다 성냥을 하나씩 써야한다.
조이는 성냥을 K개밖에 가지고 있지 않기 때문에, K번만 난로를 켤 수 있다.
하루의 시작에는 난로가 꺼져있다.
또한 난로는 켜져있는 시간만큼 연료를 소비하기 때문에, 난로를 잘 조작하여 난로가 켜져있는 시간을 최소로 하고 싶다.
조이의 방에 오는 손님의 정보와 조이가 가지고 있는 성냥의 개수가 주어졌을 때, 난로가 켜져있는 시간의 최솟값을 구하자.
입력
첫 번째 줄에 두 개의 자연수 N과 K가 공백을 사이에 두고 주어진다. N은 손님의 수를, K는 조이가 가지고 있는 성냥 개수를 의미한다.
두 번째 줄부터 N개의 줄에 손님의 방문 시간을 나타내는 자연수 T_i가 주어진다.
i번째 손님은 T_i시간에 들어와 T_i + 1시간에 나간다.
[제한]
1 ≦ N ≦ 100,000 1 ≦ K ≦ N 1 ≦ T_i ≦ 1,000,000,000 (1 ≦ i ≦ N) T_i < T_(i +1) (1 ≦ i ≦ N – 1)
1번 부분문제 (20점)
• N ≦ 20
• 1 ≦ T_i ≦ 20 (1 ≦ i ≦ N)
2번 부분문제 (30점)
• N ≦ 5,000
3번 부분문제 (50점)
• 추가 제한은 없다.
출력
예제1
32
1
3
6
4
예제2
31
1
2
6
6
예제3
33
1
3
6
3
예제4
105
1
2
5
6
8
11
13
15
16
20
12