+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- احمد $n$ شیء و $m$ جعبه دارد که هر جعبه اندازه‌اش برابر $k$ است. اشیاء به ترتیب از چپ به راست با ١ تا $n$ شماره گذاری شده‌اند و اندازه‌ی شیء $i$ام برابر $a_i$ است. با احمد می‌خواهد اشیاء را درون جعبه‌ها قرار دهد و برای این کار الگوریتم زیر را اجرا می‌کند: ابتدا یک جعبه‌ی خالی در دستش می‌گیرد و یک عدد $1 \leq j \leq n$ انتخاب می‌کند. سپس از شیء $j$ام شروع می‌کند و آن را در جعبه‌ی فعلی قرار می‌دهد و به سراغ شیء $j + 1$ام می‌رود. حال اگر شیء $j + 1$ام در جعبه‌ی فعلی بتواند قرار بگیرد، آن را در جعبه ی فعلی قرار می‌دهد. در غیر این صورت، جعبه‌ی فعلی را بسته بندی کرده و کنار می‌گذارد و جعبه‌ی خالی دیگری را برمی دارد تا شیء $j + 1$ام را در آن قرار دهد. او این کار را تا زمانی تکرار می‌کند که شیء $n$ام در جعبه‌ای قرار بگیرد و یا جعبه‌هایش تمام شود. سپس الگوریتم پایان می‌یابد. احمد می‌خواهد حتماً تمام شیءهای $j$ تا $n$ را در جعبه‌ای قرار داده باشد. بنابراین اگر هنگام قرار دادن یک شیء، آن شیء را نتواند در جعبه‌ی فعلی‌اش قرار دهد و جعبه‌های خالی‌اش نیز تمام شده باشند، به هدفش نرسیده است. به احمد کمک کنید عدد $j$ را طوری انتخاب کند که بیش ترین تعداد شیء را بتواند در جعبه‌ها قرار دهد و تمام اشیاء از $j$ تا $n$ درون جعبه‌ها قرار گرفته باشند. # ورودی در خط اول ورودی به ترتیب سه عدد صحیح $n$ و $m$ و $k$ آمده اند که تعداد اشیاء، تعداد جعبه‌ها و اندازه‌ی جعبه‌ها را نشان می‌دهند. $$1 \leq n, m \leq 2 \times 10^5$$ $$1 \leq k \leq 10^9$$ در خط بعدی، $n$ عدد $a_1, a_2, \dots, a_n\,$ آمده اند که $a_i$ نمایانگر اندازه‌ی شیء $i$ام است. $$1 \leq a_i \leq k$$ # خروجی در تنها خط خروجی، بیش ترین تعداد شیء هایی که احمد می‌تواند طبق الگوریتم گفته شده در جعبه‌ها قرار دهد چاپ کنید. # مثال‌ها ## ورودی نمونه ۱ ``` 5 2 6 5 2 1 4 2 ``` ## خروجی نمونه ۱ ``` 4 ``` ## ورودی نمونه ۲ ``` 5 1 4 4 2 3 4 1 ``` ## خروجی نمونه ۲ ``` 1 ```

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