Trong phòng của JOI-kun có một chiếc lò sưởi. Vì đã quen với trời lạnh, cậu không cần bật lò khi ở trong phòng một mình. Tuy nhiên, khi có khách, cậu phải bật lò sưởi.

Một ngày nọ, có \(N\) vị khách đến thăm JOI-kun. Vị khách thứ \(i\) (\(1\le i\le N\)) đến vào thời điểm \(T_i\) và rời đi vào thời điểm \(T_i+1\). Tại mỗi thời điểm, có nhiều nhất một vị khách ở thăm.

JOI-kun có thể bật hoặc tắt lò sưởi vào bất kỳ thời điểm nào. Mỗi lần bật lò cần dùng một que diêm. Cậu chỉ có \(K\) que diêm, nên có thể bật lò nhiều nhất \(K\) lần. Đầu ngày, lò sưởi đang tắt.

Khi được bật, lò sưởi tiêu thụ nhiên liệu. Vì vậy, JOI-kun muốn chọn các thời điểm bật và tắt sao cho tổng thời gian lò hoạt động nhỏ nhất, đồng thời lò luôn được bật khi có khách.

Cho thời gian ghé thăm của các vị khách và số que diêm, hãy tính tổng thời gian hoạt động nhỏ nhất của lò sưởi.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa hai số nguyên \(N,K\), cách nhau bởi dấu cách: số khách và số que diêm.
• Dòng thứ \(i\) trong \(N\) dòng tiếp theo chứa số nguyên \(T_i\), là thời điểm vị khách thứ \(i\) đến. Người đó rời đi vào thời điểm \(T_i+1\).

Dữ liệu ra

Ghi một dòng chứa tổng thời gian hoạt động nhỏ nhất của lò sưởi.

Ràng buộc

• \(1\le N\le100\,000\).
• \(1\le K\le N\).
• \(1\le T_i\le10^9\) với \(1\le i\le N\).
• \(T_i<T_{i+1}\) với \(1\le i<N\).

Phân nhóm

1. (20 điểm) \(N\le20\) và \(1\le T_i\le20\) với mọi \(1\le i\le N\).
2. (30 điểm) \(N\le5000\).
3. (50 điểm) Không có ràng buộc bổ sung.

Ví dụ

3 2
1
3
6

4

3 1
1
2
6

6

3 3
1
3
6

3

10 5
1
2
5
6
8
11
13
15
16
20

12

Nguồn

JOI 2017/2018, vòng chung kết, bài Stove. Đề do Japanese Committee for the International Olympiad in Informatics công bố. Đề gốc tiếng Anh. Bản dịch tiếng Việt theo CC BY-SA 4.0.