Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PKADKP - PKADKP

Học dốt toán cũng là một cái tội

 

Ngày xửa ngày xưa cái thời mà đã có điện thoại di động ^^ ở 1 vương quốc nọ có một vị vua anh minh là adkp, vị vua có có một cô công chúa đẹp tuyệt trần vừa tròn 18 tuổi . Tương truyền rằng vị vua rất kén ăn nên quyết tâm kén 1 chàng rể nấu ăn giỏi . Nghe nói nhà vua kén rể các chàng trai từ khắp mọi miền đất nước đều háo hức, kéo đến cung điện tranh tài mong sao thoát được kiếp f.a , only_love97 cx không ngoại lệ .Vốn ái mộ công chúa từ rất lâu rồi và cũng rất may là nấu ăn khá giỏi nên only_love97 tự tin rằng mình sẽ lấy được công chúa làm vợ .Thật chớ trêu thay thử thách của vua khiến anh ta phải đau đầu vì nó cần kiến thức toán học nhiều hơn là nấu ăn(anh ta học rất dốt toán ) . Only_love97 rất hối hận nhưng điều đó là quá muộn rồi . Nhưng rồi thần may mắn đã đến với anh khi vua ban cho mỗi người 3 quyền trợ giúp : 50-50 , gọi điện thoại cho người thân và hỏi ý kiến khán giả trong cung điện . Only_love97 vui sướng rút điện thoại ra và gọi ngay về cho những coder VOJ để mong sự trợ giúp , anh ta hứa sẽ hậu tạ khi được làm phò mã ^^. Hãy giúp chàng trai tội nghiệp này nhé !

Thử thách mà vua đưa ra như sau:

Cho 1 thực đơn các món ăn được đánh số từ 1 tới n món ăn thứ i có chỉ số là i và thời gian nấu các món ăn được cho là a1…an . Ở bước thứ i các đầu bếp chọn đoạn li..ri (li≤ri≤n) với điều kiện là li<>li-1 , li<>li-2 ... li <> l1; ri<>ri-1... ,ri<>r1 và (ri-li+1≤k) rồi nấu tất cả các món ăn có thời gian nấu nhỏ nhất trong các món ăn chưa được nấu thuộc đoạn đó. Nhà vua muốn biết số bước nhỏ nhất mà đầu bếp phải thực hiện để nấu tất cả các món ăn.

Input

Dòng đầu 2 số N,k(1≤K≤N≤105)

N dòng tiếp theo mỗi dòng gồm 1 số nguyên dương Ai (Ai≤10^9)

Output

1 dòng duy nhất là kết quả của bài toán

Example

Input:

3 3

1

2

2

Output: 2

Giải thích chọn đoạn là [1;2] nấu món ăn mang chỉ số là 1

Chọn đoạn [2;3] nấu món ăn mang chỉ số 2,3

Bạn không thể chọn 2 đoạn là [1;3] và [2;3] ; hay [1,2] và[1;3]


Được gửi lên bởi:LOVE VNOI
Ngày:2014-11-10
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:Đào Phan Khải

hide comments
2016-11-12 04:28:58
:v
2015-04-08 13:12:42 kivu99pro
good
2014-11-12 03:27:05 livw
code xong hau ta cong chua nhe
2014-11-11 02:28:24 ๖ۣۜGosu
Đoạn văn đầu tiên không cần đọc.
2014-11-10 17:50:16 Mew.
điều kiện li <> và ri <> kia là và hay hoặc vậy ?
2014-11-10 16:42:35 LOVE VNOI
update test + giới hạn có 1 số người mất ac thì nghĩ tinh chỉnh cho tối ưu hơn
2014-11-10 15:16:55 CHT_M
:v
2014-11-10 14:38:05 Nguyễn Thành Chinh
ok :v
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.