+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- میلاد و پارسا که از رسیدن به مرحله‌ی نهایی کدکاپ ۳ جا ماندند، از خجالت به شهر دورافتاده برره مهاجرت کردند و در آنجا مسئول بلیت فروشی سینما شدند. سینما برره دو سالن دارد که فیلم‌های متفاوتی را نشان می‌دهد و هرکدام ظرفیت $B$ نفر آدم را دارد. مردم برره، مردمی فرهیخته هستند و اعتقاد زیادی به صف دارند اما یک عادت بد دارند، هر شخص دوست دارد فیلمی را ببیند که نفر جلویی‌اش در صف می‌بیند و به صورت پیش‌فرض بلیت همان فیلم را می‌خرد مگر اینکه به او به اندازه جیبش پول بدهیم تا راضی شود فیلم دیگر را ببیند. ظرفیت جیب نفر $i$-ام در صف را با $a_i$ نشان می‌دهیم. رییس از میلاد و پارسا خواسته که طوری بلیت فروشی کنند که: ۱- برای یک سالن بیشتر از $B$ بلیت نفروشند. ۲- کمترین هزینه را صرف پر کردن جیب افراد بکنند. از شما می‌خواهیم این کمترین هزینه را برای میلاد و پارسا، دو دوست مهربان قصه‌ی ما، حساب کنید. تضمین می‌شود که حتما می‌توانیم طوری $n$ نفر را بین سالن‌ها پخش کنیم که در هیچ‌یک از دو سالن بیشتر از $B$ نفر نرود. # ورودی در خط اول $n$ که تعداد افراد صف است و $B$ که ظرفیت سالن‌هاست به شما داده می‌شود. در خط بعدی $n$ عدد داده می‌شود که عدد $i$-ام اندازه جیب نفر $i$-ام یا همان $a_i$ است. $$ 1 \le n \le 3\ 000$$ $$ 0 \le a_i \le 10^9 $$ $$n \le 2 \times B$$ # خروجی در یک خط کمترین هزینه لازم برای برآورده کردن شرط‌ها را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 2 1 1000 50 ``` ## خروجی نمونه ۱ ``` 50 ``` ## ورودی نمونه ۲ ``` 3 2 50 10 1000 ``` ## خروجی نمونه ۲ ``` 10 ```

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