+ الزمن المحدد: 0.5 ثانية + حد الذاكرة: 256 ميجابايت ---------- بعد أن لم يذهب أي من الطلاب الـ $k$ الخاصين بالسيد ربيع إالى الرحلة بسببه، قرر أن يشجعهم عن طريق الذهاب معهم إلى محل حلويات وشراء كعكة لهم. بعد وصولهم إلى المحل، أصيب السيد ربيع بدهشة عند رؤية أسعار الكعك في المحل. ولكنه بما أنه كان يحب طلابه كثيراً، قرر أن يشتري الكعك بالتأكيد. كونه معلم رياضيات، فكر في كيفية جعل الطلاب سعداء وفي الوقت نفسه تقليل التكلفة بالنسبة لنفسه. في معرض الحلويات، تم ترتيب $n$ كعكة بجوار بعضهم، حيث تكلف الكعكة رقم $i$ مبلغ $c_i$. اتخذ السيد ربيع قرارًا بتقسيم الكعك إلى $k$ فترات **متتالية** (يجب أن تكون كل كعكة في فترة او نطاق واحد بشكل دقيق) وأخبر الطالب رقم $i$ بأنه يجب عليه اختيار واحدة من بين الكعك في الفترة رقم $i$ كألذ كعكة (يعتبر الكعك الألذ من بين الكعك التي تكون **أغلى سعرًا** وإذا كان هناك عدة كعك بنفس السعر الأعلى، فيمكن للطالب اختيار أي واحد منها حسب رغبته). في النهاية، يختار واحدة من الـ $k$ الكعك التي اختارها الطلاب، وهي الكعكة التي في الواقع **أرخصهم**، ويشتريها لهم. يجب عليك في هذا السياق أن تجد حلاً يمكن للسيد ربيع من خلاله تصنيف الكعك بحيث يمكنه تحويل المال بأقل مبلغ ممكن في النهاية، وعليك طباعة هذا المبلغ المطلوب. في الواقع، يجب أن تجد طريقة لتصنيف الكعك حيث تكون أصغر كمية هي الأقل الممكنة من بين الحد الأقصى لهذه الفئات وطباعة هذه الكمية. # الإدخال في السطر الأول، يتم ذكر رقمين هما $n$ و $k$، حيث يمثلان بالترتيب عدد الكعك وعدد الطلاب. في السطر الثاني، يتم ذكر $n$ أرقام، حيث يمثل الرقم $i$ عدد $c_i$. $$ 1 \le k \le n \le 5\ 000 $$ $$ 1 \le c_i \le 5\ 000$$ # الإخراج في سطر واحد من الإخراج، قم بطباعة المبلغ الذي سيقوم السيد ربيع بدفعه. # مثال ## نموذج إدخال 1 ``` 5 1 10 45 23 32 8 ``` ## نموذج إخراج 1 ``` 8 ``` ## نموذج إدخال 2 ``` 7 4 10 5 2 2 3 22 100 ``` ## نموذج إخراج 2 ``` 2 ```