Đầu bếp the Chef mơ thấy mình lạc vào một cuộc thi nấu ăn rấ kì lạ, nơi mà chất lượng món ăn không quan trọng bằng thời gian bạn hoàn thành nó. Mỗi đầu bếp tham gia cuộc thi phải nấu đủ n món ăn ở n vị trí tạo thành một hàng dọc (để thuận tiện ta đánh số các món ăn từ 1 đến n từ đầu hàng đến cuối hàng). Món ăn thứ i sẽ mất ai thời gian để nấu. Các thi sinh sẽ chơi theo nhiều lượt cho đến khi họ nấu đủ n món ăn. Khó khăn hơn, ở mỗi lượt họ phải chọn K vị trí liên tiếp và nấu hết các món ăn chưa được nấu với thời gian nấu nhỏ nhất trong đó. Ví dụ nếu dãy món ăn có 5 món và có thời gian nấu lần lượt là 4, 3, 4, 3, 4 độ dài mỗi đoạn đồ ăn trong mỗi lượt chơi là 3. Ở lượt đầu tiên nếu chọn đoạn [2, 4] the Chef sẽ nấu được hai món có thởi gian nấu là 3. Lượt thứ hai ông ta chọn đoạn [1, 3] để nấu hai đồ ăn có thời gian nấu là 4 và dùng lượt cuối cùng chọn đoạn [3, 5] để nấu đồ ăn thứ 5. Ai dùng ít lượt chơi nhất sẽ là người chiến thắng. Bạn hãy tính giúp đầu bếp the Chef số lượt chơi ít nhất mà ông ta có thể dùng.

Dữ liệu vào:

Dòng 1: Ghi 2 số nguyên dương N và K (1 ≤ K ≤ N ≤ 100,000).

N dòng tiếp theo: Mỗi dòng ghi một số nguyên không âm Ai không quá 1,000,000,000 là thời gian nấu món ăn thứ i.

Dữ liệu ra:

Ghi ra kết quả tìm được.

Sample Input

5 3
40
30
40
30
40

Sample Output

3