조이의 집에는 난로가 하나 있다. 

조이는 추위에 강하기 때문에 집에 혼자 있을 때는 난로를 켜지 않아도 되지만, 손님이 오면 난로를 켜야 한다.

오늘, 조이의 집에는 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번 예제에서는 조이의 방에 3명의 손님이 온다.

다음과 같이 난로를 조작하면 손님이 있는 동안 난로가 켜져있고, 난로를 켜는 횟수는 2 회이며, 난로가 켜져있는 시간은 총 (4 - 1) + (7 - 6) = 4이다. 

• 첫 번째 손님이 오는 시간 1에 난로를 켠다. 

• 두 번째 손님이 나가는 시간 4에 난로를 끈다. 

• 세 번째 손님이 오는 시간 6에 난로를 켠다. 

• 세 번째 손님이 나가는 시간 7에 난로를 끈다. 난로가 켜져있는 시간을 4보다 짧게 만들 수 없기 때문에 4를 출력한다. 

2번 예제에서는 조이가 난로를 딱 한 번 켤 수 있기 때문에, 첫 번째 손님이 오는 시간 1에 난로를 켜고 3번째 손님이 나가는 시간 7에 난로를 끄면 된다. 손님이 나가는 시간과 그 다음 손님이 들어오는 시간이 일치하는 경우가 있음에 유의하라.

3번 예제에서는 손님이 도착 할 때마다 난로를 켜고 손님이 나갈 때마다 난로를 끄면 된다.