- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
احمد $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
ارسال پاسخ برای این سؤال