+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- پس از اینکه هر $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 ``` در این مثال آقا فیروز تنها یک شاگرد دارد و مجبور است تمامی کیک‌ها را یک بازه در نظر بگیرد و در این صورت شاگردش نیز گران‌ترین کیک یعنی کیک با قیمت ۴ را انتخاب می‌کند. <details class="blue"> <summary> راهنمایی ۱ </summary> مساله را بر حسب $k$ به سه حالت زیر تقسیم کنید: + $k = 1$ + $k = 2$ + $k \ge 3$ سپس برای هر یک از این سه حالت جواب مساله را بر حسب رابطه‌ای از آرایه به دست آورید. </details> <details class="blue"> <summary> راهنمایی ۲ </summary> به ازای $k = 1$ تنها به یک حالت می‌توان آرایه را بازه‌بندی کرد و به همین دلیل جواب برابر با عنصر بیشینه آرایه است؛ در حالت $k \ge 3$ هم می‌توان طوری بازه‌بندی را انجام داد که عضو کمینه در یک بازه بیفتد و بنابراین جواب این حالت برابر با عضو کمینه آرایه است. حال تنها حالت $k = 2$ باقی می‌ماند که باید آن را حل کنید. </details> <details class="blue"> <summary> راهنمایی ۳ </summary> در حالت $k = 2$ جواب برابر کمینه عضو اول و آخر آٰرایه است؛ چون می‌توانید آرایه را طوری دسته‌بندی کنید که یکی از این اعضا در یک دسته قرار بگیرد. هم‌چنین در هر حالتی از دسته‌بندی می‌توان این دو را به عنوان کیک خوشمره انتخاب کرد و بنابراین جواب نمی‌تواند کم‌تر شود. </details>

حل سؤال در بانک سؤالات