+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- پس از اینکه هر $k$ شاگرد آقا فیروز به‌خاطر او،‌ به مسافرت نرفتند؛ او برای اینکه آن‌ها را تشویق کند، تصمیم گرفت تا به همراه آن‌ها به قنادی کاف برود و برایشان کیک بخرد. پس از اینکه وارد قنادی شدند، آقا فیروز از دیدن قیمت کیک‌ها خیلی جا خورد ولی چون شاگردانش را خیلی دوست داشت، تصمیم گرفت حتما کیک را بخرد. او که معلم ریاضی بود با خود فکری کرد که هم شاگردان خوشحال باشند و هم خودش هزینه کم‌تری کند. در ویترین قنادی $n$ کیک کنار هم چیده شده که قیمت $i$امین آن‌ها $c_i$ است. آقا فیروز تصمیم گرفت تا کیک‌ها را به $k$ بازه **متوالی** تقسیم کند (هر کیک باید در دقیقا یک بازه باشد) و به شاگرد $i$ام بگوید بین کیک‌های بازه $i$ام یکی را که خوش‌مزه‌تر است انتخاب کند(هر کدام از شاگردان، کیکی را به عنوان خوش‌مزه‌ترین انتخاب می‌کند که از همه **گران‌تر** است و در صورتی که چند کیک با گران‌ترین قیمت وجود داشت، به دلخواه یکی از آن‌ها را انتخاب می‌کند). در نهایت او از بین $k$ کیکی که شاگردان انتخاب کردند، یکی از آن‌ها که در واقع **ارزان‌ترینشان** است را انتخاب می‌کند و برای آن‌ها می‌خرد. می‌دانیم در این ایام رعایت بهداشت ضروری است و به همین دلیل، آقا فیروز مشغول نصب [همراه‌بانک مهر ایران](http://www.asredanesh.com/products-services/e-financial/e-banking/gh-mehr-mobile-bank/) برای تلفن همراه خود است تا بتواند پول کیک را به صورت آنلاین و بدون رد و بدل کردن پول نقد پرداخت کند. در این فاصله شما باید راهکاری پیدا کنید که آقا فیروز کیک‌ها را دسته‌بندی کند که در نهایت کم‌ترین مقدار پول ممکن را کارت به کارت کند و این مقدار پول لازم را چاپ کنید. در واقع شما باید راهکاری برای دسته‌بندی کیک‌ها پیدا کنید که در آن کم‌ترین مقدار، میان بیشینه این دسته‌ها، کم‌ترین مقدار ممکن باشد و این مقدار را چاپ کنید. # ورودی در خط اول دو عدد $n$ و $k$ آمده است که به ترتیب نمایانگر تعداد کیک‌ها و تعداد شاگرد‌ها می‌باشند. در خط دوم $n$ عدد آمده‌ است که عدد $i$ام نمایانگر $c_i$ است. $$ 1 \le k \le n \le 5\ 000 $$ $$ 1 \le c_i \le 5\ 000$$ # خروجی در تنها خط خروجی، مقدار پولی که آقا فیروز می‌پردازد را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 3 2 3 2 3 ``` ## خروجی نمونه ۱ ``` 3 ``` در این مثال هر گونه آقا فیروز کیک‌ها را بازه‌بندی کند، یک بازه به طول ۱ و یک بازه به طول ۲ ایجاد می‌شود که در هر دوی آن‌ها قیمت گران‌ترین کیک برابر ۳ است و بنابراین او راهی به جز پرداخت ۳ واحد پول ندارد. ## ورودی نمونه ۲ ``` 5 3 5 4 3 2 2 ``` ## خروجی نمونه ۲ ``` 2 ``` در این مثال آقا فیروز می‌تواند هر کدام از عناصر کناری را یک بازه و سه عنصر وسط را هم یک بازه در نظر بگیرد. در این صورت شاگردها کیک‌هایی با قیمت‌های ۵، ۴ و ۲ را پیشنهاد می‌دهند که او می‌تواند کیک با قیمت ۲ را بخرد و کمترین مقدار ممکن را پرداخت کرده است چون کیکی با قیمت کمتر وجود ندارد. ## ورودی نمونه ۳ ``` 4 1 1 3 4 2 ``` ## خروجی نمونه ۳ ``` 4 ``` در این مثال آقا فیروز تنها یک شاگرد دارد و مجبور است تمامی کیک‌ها را یک بازه در نظر بگیرد و در این صورت شاگردش نیز گران‌ترین کیک یعنی کیک با قیمت ۴ را انتخاب می‌کند.