+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- **می‌توانید شعر زیر را نخوانید و تاثیری در فهم سوال ندارد.** توی ده [شلمرود](https://quera.ir/problemset/technology/33127/%D8%B3%D8%A4%D8%A7%D9%84-%D9%81%D8%B1%D8%A7%D9%86%D8%AA-%D8%A7%D9%86%D8%AF-%D8%B4%D9%84%D9%85%D8%B1%D9%88%D8%AF) حسنی تک و تنها بود حسنی نگو بلا بگو تنبل تنبل‌ها بگو موی بلند، روی سیاه ناخن دراز، واه و واه و واه نه فلفی، نه قلقلی نه مرغ زرد کاکلی هیچکس باهاش رفیق نبود تنها روی سه پایه، نشسته بود تو سایه باباش می‌گفت: حسنی میای بریم حموم؟ «نه نمیام، نه نمیام» سرت رو می‌خوای اصلاح کنی؟ «نه نمی‌خوام، نه نمی‌خوام» کره الاغ کدخدا یورتمه می‌رفت تو کوچه‌ها «الاغه چرا یورتمه میری؟» «دارم می‌رم بار ببرم دیرم شده عجله دارم» «الاغ خوب و نازنین سر در هوا سم بر زمین یالت بلند و پرمو دمت مثال جارو یک کمی به من سواری میدی؟» «نه که نمی‌دم» «چرا نمی‌دی؟» «واسه این که من تمیزم پیش همه عزیزم اما تو چی؟ موی بلند، روی سیاه ناخن دراز، واه و واه و واه!» غازه پرید تو استخر «تو اردکی یا غازی؟» «من غاز خوش زبانم» «میای بریم به بازی؟» «نه جانم» «چرا نمیای؟» «واسه این که من صبح تا غروب میون آب، کنار جو مشغول کار و شستشو اما تو چی؟ موی بلند، روی سیاه ناخن دراز، واه و واه و واه» در وا شد و یه جوجه دوید و اومد تو کوچه جیک‌جیک‌کنان گردش‌زنان اومد و اومد پیش حسنی «جوجه کوچولو کوچول موچولو میای با من بازی کنی؟» مادرش اومد «قدقدقدا برو خونتون تو رو به خدا جوجه‌ی ریزه میزه ببین چقد تمیزه؟ اما تو چی؟ موی بلند، روی سیاه ناخن دراز، واه و واه و واه» حسنی با چشم گریون پا شد و اومد تو میدون «آی فلفلی، آی قلقلی میاین با من بازی کنین؟» «نه که نمیایم» «چرا نمیاین؟» فلفلی گفت: من و داداشم و بابام و عموم هفته‌ای دو بار میریم حموم اما تو چی؟ قلقلی گفت: نگاش کنین موی بلند، روی سیاه ناخن دراز، واه و واه و واه حسنی دویید پیش باباش «حسنی میای بریم حموم؟» «میام، میام» «سرتو میخوای اصلاح کنی؟» «میخوام، میخوام» حسنی نگو یه دسته گل تر و تمیز و تپل مپل الاغ و خروس و جوجه غاز و ببعی با فلفلی با قلقلی با مرغ زرد کاکلی حلقه زدن دور حسن الاغه می‌گفت: اگر کاری نداری بریم الاغ سواری خروسه می‌گفت: قوقولی قوقو، قوقولی قوقو هر چی میخوای، فوری بگو مرغه می‌گفت: حسنی برو تو کوچه بازی بکن با جوجه غازه می‌گفت: حسنی بیا با همدیگه بریم شنا توی ده شلمرود حسنی دیگه تنها نبود! ---------- بعد از این که حسنی تمیز شد و با همه بازی کرد، همه دور هم جمع شدند و از بابای حسنی خواستند که ازشون عکس بگیره. ولی وقتی بابای حسنی اومد، فهمیدند که حداکثر $k$تاشون درون یه عکس جا می‌شوند. بابای حسنی گفت: «خب حالا عیبی نداره، $k$تا $k$تا بیایید ازتون عکس می‌گیرم.» مرغه گفت: «این‌طوری که نمی‌شه، من می‌خوام با جوجه‌هام توی یه عکس باشم.» الاغه گفت: «تازه من هم می‌خوام با خروسه توی یه عکس باشم. اگه این‌طوریه، من اصلا عکس نمی‌گیرم.» بابای حسنی یه ذره مِن‌و‌مِن کرد و گفت: «خب عیبی نداره. شما بیایید توی یه صف وایسید، بعد هم تا جایی که جا شدید می‌آیید توی عکس» بالاخره اهالی ده شلمرود تصمیم گرفتند که به $n$تا دسته تقسیم بشوند و توی دسته‌ی $i$ام $a_i$نفر بودند که می‌خواستند با هم عکس بگیرند. حالا بابای حسنی از شما می‌پرسد که حداقل باید چند تا عکس بگیرد تا همه در یک عکس افتاده باشند. در هر عکسی که بابای حسنی می‌گیرد یک بازه پشت سر هم از دسته‌ها می‌توانند حضور داشته باشند که جمع اعضای این بازه باید حداکثر $k$ باشد. در واقع شما یه آرایه‌ی $n$تایی دارید و باید بگید حداقل $m$ چقدر هست که بتوان آرایه‌ را به $m$ بازه تقسیم کرد که مجموع اعداد هر بازه حداکثر $k$ باشد. *توجه کنید که بازه به دنباله‌ای متوالی از اعضای یک آرایه گفته می‌شود.* # ورودی ورودی شامل دو خط است. در خط اول به ترتیب ابتدا $n$ تعداد گروه‌ها و سپس $k$ حداکثر ظرفیت یک عکس به شما داده می‌شود. در خط دوم $n$ عدد به شما داده می‌شود که عدد $i$ام آن‌ها، $a_i$ است. $$ 1 \le n, k \le 100\ 000$$ $$0 \le a_i \le k$$ # خروجی خروجی برنامه شامل یک عدد صحیح است، حداقل تعداد عکس‌هایی که پدر حسنی باید بگیرد. # مثال ## ورودی نمونه ۱ ``` 5 4 3 4 1 2 2 ``` ## خروجی نمونه ۱ ``` 4 ``` بازه‌ها به صورت $\{3\}, \{4\}, \{1, 2\}, \{2\}$ خواهند بود. یک جواب دیگر برای این مثال $\{3\}, \{4\}, \{1\}, \{2, 2\}$ است. ## ورودی نمونه ۲ ``` 5 8 3 4 1 2 2 ``` ## خروجی نمونه ۲ ``` 2 ``` --------------------------- <details class="blue"> <summary> راهنمایی ۱ </summary> اگر دسته اول و دوم نتوانند در یک عکس باشند، (یعنی $a_1+a_2 \gt k$) حتما دسته اول باید تنهایی عکس بگیرند و با دسته دیگری نمی‌توانند در یک عکس باشند. </details> <details class="blue"> <summary> راهنمایی ۲ </summary> در چه صورت جواب بهینه‌ای وجود دارد که دسته اول و دوم هر دو در یک عکس باشند؟ </details> <details class="blue"> <summary> راهنمایی ۳ </summary> ثابت کنید اگر دسته دوم می‌توانست در عکس با دسته اول باشد (یعنی $a_1+a_2 \le k$) جواب بهینه‌ای وجود دارد که دسته اول و دوم هر دو در یک عکس باشند. </details> <details class="blue"> <summary> راهنمایی ۴ </summary> اگر دسته اول و دوم با هم نمی‌توانستند در یک عکس باشند، یک عکس تکی از دسته اول بگیرید. اگر دسته اول و دوم می‌توانستند با هم باشند، این دو دسته را یک دسته جدید با اندازه $a_1+a_2$ در نظر بگیرید و مسئله را دوباره حل کنید. </details> <details class="blue"> <summary> راه حل </summary> دسته اول را در عکس اول قرار بدهید. سپس دسته دوم را اگر می‌شد، در عکس قرار بدهید، سپس دسته سوم و به همین روال ادامه دهید تا زمانی که دیگر نمی‌توانید دسته جدیدی قرار بدهید. فرض کنید *t* دسته اول را در عکس اول قرار دادید و نمی‌توانید دسته بعدی را در عکس قرار بدهید. حالا *t* دسته اول حذف شدند و با همین روش بقیه افراد را در عکس قرار بدهید. در واقع از اولین دسته شروع کنید و تاجایی که می‌توانید دسته‌ها را در داخل عکس قرار بدهید. اثبات درستی به صورت خلاصه این است که در هر مرحله اگر دسته‌ای رو می توانید قرار بدهید. دلیلی وجود ندارد که قرار ندهید و عکس بگیرید چون این دسته باید در عکس بعدی قرار بگیرد و می‌توانست در عکس اول باشد و در عکس دوم نباشد. درستی الگوریتم را با استقرا نیز می‌توانید اثبات کنید چون دسته اول و دوم را در صورت امکان می‌توانید یک دسته بکنید و تعداد دسته‌ها کم می‌شود. </details>