Komanda işi#10401
Öz sevimli bayramı üçün Farmer John dostlarına hədiyyələr göndərmək istəyir. Hədiyyələri bükməkdə o qədər də mahir olmadığından, inəklərinin köməyinə müraciət etmək istəyir. Gözlənildiyi kimi, inəklər də hədiyyələri bükməkdə özlərindən çox da yaxşı deyillər — bu dərsi Farmer John çətin yolla öyrənmək üzrədir.
Farmer John-un inəyi sırada dayanıb, rahatlıq üçün -dən -ə qədər nömrələnmişdir. -ci inəyin hədiyyə bükmə bacarıq səviyyəsi s_i-dir. Bu bacarıq səviyyələri xeyli fərqli ola bilər, buna görə də FJ inəklərini komandalara bölmək qərarına gəlir. Bir komanda ən çox ardıcıl inəkdən ibarət ola bilər və heç bir inək birdən çox komandaya aid ola bilməz. İnəklər bir-birindən öyrəndiklərinə görə, bir komandadakı bütün inəklərin bacarıq səviyyəsi həmin komandadakı ən bacarıqlı inəyin bacarıq səviyyəsinə qədər qaldırıla bilər.
FJ-yə komandaları optimal şəkildə təşkil edərək əldə edə biləcəyi maksimum mümkün bacarıq səviyyələri cəmini tapmaqda kömək edin.
Birinci sətirdə iki tam ədəd və k~(1 \le n \le 10^4, 1 \le k \le 10^3) verilir. Növbəti sətirin hər birində inəklərin düzüldüyü sıraya uyğun olaraq bir inəyin bacarıq səviyyəsi verilir. Hər bir bacarıq səviyyəsi 10^5-i keçməyən müsbət tam ədəddir.
FJ-nin inəkləri ardıcıl komandalara bölməklə əldə edə biləcəyi maksimum mümkün bacarıq səviyyələri cəmini bildirən bir tam ədəd çap edin.
Bu nümunədə optimal həll ilk inəyi və son inəyi qruplaşdırmaqdır, ortadakı inək isə tək başına bir komandada qalır (unutmayın ki, -dan az sayda inəkdən ibarət komandalara da icazə verilir). Nəticədə, inəyin bacarıq səviyyələri , , , , , , olur ki, bu da cəmi edir.
Nümunə 1