Mô tả và yêu cầu

Trong studio của Koi có một chiếc đèn spotlight. Khi không có khách thì Koi
không cần bật đèn, nhưng hễ có khách đang chụp ảnh thì đèn bắt buộc phải sáng suốt
thời gian đó. Hôm nay có 𝑛 khách đến lần lượt theo thứ tự thời gian. Khách thứ 𝑖 đến
vào thời điểm nguyên 𝑡𝑖 và rời đi sau đúng 1 đơn vị thời gian, tức là rời đi ở thời điểm
𝑡𝑖+ 1. Các khoảng thời gian chụp không chồng lấn nhau (tại mọi thời điểm nhiều nhất
chỉ có một khách), và có thể có trường hợp khách trước vừa rời đi đúng lúc khách sau
đến.
Koi có thể bật hoặc tắt đèn bất cứ lúc nào. Tuy nhiên, mỗi lần bật đèn sẽ tốn 1 “pin
chớp”, mà Koi chỉ có 𝑘 pin, nên cả ngày chỉ được bật đèn tối đa 𝑘 lần. Ban đầu đèn đang
tắt. Vì đèn sáng càng lâu càng tốn điện, Koi muốn chọn cách bật/tắt sao cho đèn luôn
sáng trong mọi khoảng từ 𝑡𝑖 đến 𝑡𝑖 + 1 của từng số khách, số lần bật không vượt quá 𝑘,
và tổng thời gian đèn sáng là nhỏ nhất.
Dữ liệu vào: Cho trong tệp tin văn bản KOI.INP gồm
 Dòng đầu tiên gồm hai s ố nguyên dương 𝑛 và 𝑘 (1 ≤ 𝑛 ≤ 105, 1 ≤ 𝑘 ≤ 𝑛);
 𝑛 dòng tiếp theo, dòng thứ 𝑖 chứa số nguyên 𝑡𝑖 ( 1 ≤ 𝑡𝑖 ≤ 109, 𝑡𝑖 < 𝑡𝑖 + 1),
khách thứ 𝑖 đến lúc 𝑡𝑖 và rời đi lúc 𝑡𝑖 + 1.
Kết quả ra: Ghi ra tệp tin văn bản KOI.OUT gồm một số nguyên là tổng thời gian đèn
sáng nhỏ nhất.

Ví dụ

KOI.INP           KOI.OUT                                     Giải thích
   6 3               7                  -    Có 6 khách đến lúc 1, 2 , 4 , 7 , 8 , 12, mỗi khách
   1                                    chụp đúng 1 đơn vị thời gian nên các đoạn là [1,2],
   2                                    [2,3],[4,5],[7,8],[8,9],[12,13]
   4                                    -    Khoảng trống giữa các đoạn liên tiếp là: 0,1,2,0,3
   7                                    Chỉ được bật tối đa 3 lần nên phải gộp các lượt;         khi gộp
   8                                    sẽ  phải  sáng  thêm  ở  một  số  khoảng  trống.  Với  dãy
   12                                   0,1,2,0,3, phần phát sinh ít nhất là 1, nên tổng nhỏ nhất là
                                        6 + 1 = 7 (vì có 6 khách, mỗi khách cần sáng 1 đơn vị).
Ràng buộc:
         Subtask 1   : Có 50% s   ố điểm tương     ứng 50% số test với 𝑛      ≤  20 , 1  ≤  𝑡𝑖 ≤  20;
         Subtask 2: Có 30% số điểm tương ứng 30% số test với 𝑛                 ≤  5000;
         Subtask 3: Có 20% số điểm tương ứng 20% số test không ràng buộc gì thêm.