Karvanlar#1894
"Salam. Mənim adım Kyrylodur. İstərdim ki, aşağıdakı konseptdə 3D aksiyon oyunu hazırasınız... Oyunçular meşə elfləri, saray mühafizəçiləri və ya oğru olmaq arasında seçim edə bilirlər. Elflərlə oynayarkən, onlar meşədə taxta evlərdə yaşayır və saray əsgərləri və oğrular tərəfindən hücuma məruz qalırlar. Oyunçular karvanlara hücum edə bilirlər... [kəsildi] P.S. Mən iki ildir ki, belə bir oyun arzulayıram."
MiST land oyun şirkətinə məktub
Təbii ki, Petryk inkişaf prosesində qlobal oyun icmasının arzusunu nəzərə almamış qala bilməzdi. Buna görə də onun oyununda oyunçular "karvanlara hücum edə" və "karvanlardan qənimət ələ keçirə" bilirlər. Karvan arabalardan ibarətdir, hər birində müəyyən miqdarda qızıl olur. Hücum istənilən arabadan başlaya bilər və sonra növbəti və ya əvvəlki arabaya davam etdirilə bilər, orada olan qızıl yığılır. Əməliyyat tez həyata keçirilməlidir, əks halda mühafizəçilər gəlib oğruları yaxalayacaq. Nəticədə bütün arabalardan qənimət toplamaq mümkün olmayacaq.
Hər kəsin gözlədiyi kimi elflərlə oynayan Kolya karvanda arabalərin sayı , hər arabada olan qızılın miqdarı (-ci arabada a_i qızılı var) və dəstəsinin mühafizəçilər gəlməmiş maksimum neçə araba qarət edə biləcəyini () bilir. O, hücum zamanı toplanıla biləcək maksimum qızılın miqdarını müəyyən etməlidir.
Birinci sətirdə iki tam ədəd və (1 \leq k \leq N \leq 100000) — karvanda arabalərin sayı və qarət etmək mümkün olan maksimum araba sayı verilir. İkinci sətirdə ədəd a_i var, hər arabada olan qızılın miqdarı (0 \leq a_i \leq 10000).
Bir sətirdə hücum nəticəsində əldə edilə biləcək maksimum qızılın cəmini çap edin.
Nümunə 1