- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
میلاد و پارسا که از رسیدن به مرحلهی نهایی کدکاپ ۳ جا ماندند، از خجالت به شهر دورافتاده برره مهاجرت کردند و در آنجا مسئول بلیت فروشی سینما شدند.
سینما برره دو سالن دارد که فیلمهای متفاوتی را نشان میدهد و هرکدام ظرفیت \(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