Karvanlar
"Salam. Mən Kirilo. İstərdim ki, siz bir oyun hazırlayasınız, 3D-ekşn janrında... İstifadəçi meşə elfləri, saray mühafizəçiləri və ya oğru kimi oynaya bilər. Əgər istifadəçi elflərlə oynayırsa, elflər meşədə, taxta evlərdə yaşayır, saray əsgərləri və oğrular isə onlara hücum edir. Karvanları qarət etmək mümkündür... [skipped] P.S. Mən iki ildir belə bir oyun istəyirəm.
MiST land oyun inkişafı şirkətinə məktub
Və əlbəttə ki, Petryk dünya oyunçularının istəklərini nəzərə almadan inkişaf edə bilməzdi, buna görə də onun oyununda "hücum etmək" və "karvanları qarət etmək" mümkündür. Karvan arabalarından ibarətdir, hər birində müəyyən miqdarda qızıl var. Qarətə istənilən arabadan başlamaq, sonra növbəti və ya əvvəlki arabalara keçərək oradakı qızılları götürmək olar. Bütün əməliyyatı kifayət qədər tez həyata keçirmək lazımdır, əks halda mühafizəçilər gəlib oğruları tutacaq. Buna görə də bütün arabalardan qızıl götürmək mümkün olmayacaq.
Kolia, gözlənildiyi kimi, elflər üçün oynayır və karvanda arabaların sayını N, hər arabada nə qədər qızıl olduğunu (i-ci arabada a_i qızıl var) və mühafizəçilər gələnə qədər dəstəsinin keçə biləcəyi maksimum araba sayını k bilir. O, əməliyyat nəticəsində əldə edə biləcəyi maksimum qızıl miqdarını öyrənməlidir.
Giriş verilənləri
Birinci sətirdə karvanın ölçüsünü və qarət edilə biləcək maksimum araba sayını müəyyən edən iki tam ədəd N və k (1 ≤ k ≤ N ≤ 100000) verilir. İkinci sətirdə arabalardakı qızıl miqdarını müəyyən edən N tam ədəd a_i verilir (0 ≤ a_i ≤ 10000).
Çıxış verilənləri
Yeganə sətirdə qarət nəticəsində əldə edilə biləcək ən böyük məbləği göstərin.