İlanlar#10322
Əfsanəyə görə, Müqəddəs Patrik min ildən çox əvvəl Mooland-dakı bütün ilanları qovub. Lakin, sonradan ilanlar yenidən Mooland-a qayıdıblar! Müqəddəs Patrik günü martın -də idi, buna görə də Bessie Müqəddəs Patriki yad etmək üçün Mooland-dakı bütün ilanları birdəfəlik qovmağa qərar verib.
Bessie ilanları bir xətt üzərində qrupda tutmaq üçün tora malikdir. O, hər bir qrupdakı bütün ilanları, qrupların xətdəki ardıcıllığı ilə tutmalıdır. Hər dəfə Bessie bir qrupu tutanda, ilanları qəfəsə yerləşdirə və növbəti qrup üçün torunu boş halda başlaya bilər.
Toru ölçüsündə olduqda, Bessie istənilən g \leq s sayda ilan olan qrupu tutub, amma hər dəfə sayda ilanı ölçülü torla tutanda, s-g qədər boş yer itirir. Bessie torunun ölçüsünü istədiyi dəyərdə başlada və onu dəfə dəyişə bilər.
Zəhmət olmasa, bütün ilanları tutduqdan sonra Bessie-nin toplam ən az nə qədər boş yer itirəcəyini müəyyən edin.
Birinci sətirdə (1 \leq n \leq 400) və (1 \leq k < n) ədədləri verilir. İkinci sətirdə tam ədəd a_1, \ldots, a_n (burada a_i (0 \leq a_i \leq 10^6) -ci qrupdakı ilanların sayını göstərir) verilir.
Bütün ilanları tutduqdan sonra Bessie-nin toplam ən az nə qədər boş yer itirəcəyi bir tam ədəd kimi çıxışa verilir.
\begin{example}\exmp{6 27 9 8 2 3 2}{3}%\end{example}
Nümunə 1
Bessie torunu ölçüsündə başlayır. Birinci qrupun ilanlarını tutduqdan sonra, torun ölçüsünü -a dəyişir və bu ölçüdə qalır, ta ki 4-cü qrupun ilanlarını tutanda, torunu ölçüsündə edir. Toplam itirilən boş yer (7 - 7) + (9 - 9) + (9 - 8) + (3 - 2) + (3 - 3) + (3 - 2) = 3 olur.