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

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

오늘, 조이의 집에는 N명의 손님이 온다.

i번째 (1 ≦ i ≦ N) 손님은 시간 T_i에 와서 시간 T_i + 1에 나간다.

같은 시간에 2명 이상의 손님이 조이의 집에 있는 경우는 없다.

조이는 임의의 시간에 난로를 껐다 켰다 할 수 있다.

그러나 난로를 켤 때마다 성냥을 하나씩 써야한다.

조이는 성냥을 K개밖에 가지고 있지 않기 때문에, K번만 난로를 켤 수 있다.

하루의 시작에는 난로가 꺼져있다.

또한 난로는 켜져있는 시간만큼 연료를 소비하기 때문에, 난로를 잘 조작하여 난로가 켜져있는 시간을 최소로 하고 싶다.

조이의 방에 오는 손님의 정보와 조이가 가지고 있는 성냥의 개수가 주어졌을 때, 난로가 켜져있는 시간의 최솟값을 구하자.

난로 timer 1초 memory 256MB

난로 1초 256MB