- محدودیت زمان: ۰.۵ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
- منبع: آزمون نهایی اول دوره ۲۷ المپیاد کامپیوتر
السا و مهرسا می‌خواهند میوه‌ها را برای مراسم آماده کنند. السا وظیفه شستن میوه‌ها را بر‌عهده دارد و مهرسا باید میوه‌ها را در ظرف قرار دهد. $n$ میوه داریم که در پشته یک قرار دارند و میوه‌ها از سر پشته تا ته پشته از $1$ تا $n$ شماره گذاری شده‌اند.
هر بار السا می‌تواند یک میوه از سر پشته‌ی یک (در صورتی که خالی نباشد) بردارد و بشورد سپس در پشته‌ی دو قرار دهد.
مهرسا نیز می‌تواند یک میوه از سر پشته‌ی دو (در صورتی که خالی نباشد) برداشته و سپس در ظرفی که هم اکنون جلوی او قرار دارد بگذارد یا ظرفی که جلویش هست را کنار گذاشته و از ظرف خالی دیگری استفاده کند (مهرسا دیگر نمی‌تواند از ظرفی که کنار گذاشته است استفاده کند).
هر ظرف تنها تحمل $k$ کیلوگرم میوه را دارد و جمع وزن میوه‌هایی که مهرسا در یک ظرف می‌گذارد نباید از $k$ کیلوگرم بیشتر باشد.
آنها می‌خواهند طوری این میوه‌ها را در ظرف‌ها قرار دهند که کمترین تعداد ظرف ممکن استفاده شود. این کمینه را برای آنها بیابید.
ورودی
در خط اول ورودی عدد $n$، تعداد میوه‌ها، و $k$ حداکثر تحمل یک ظرف، آمده است.
در خط دوم $n$ عدد آمده است که عدد $i$ام، $w_i$، وزن میوه $i$ام را نشان می‌دهد. $$1 \le n, k \le 70$$ $$1 \le w_i \le k$$
خروجی
در تنها خط خروجی حداقل تعداد ظرف لازم برای اینکه میوه‌ها در ظرف‌ها قرار داده شوند را چاپ کنید.
زیرمسئله‌ها
| زیرمسئله | نمره | محدودیت |
|---|---|---|
| ۱ | ۲ | $k = 1$ |
| ۲ | ۸ | $k \le 2$ |
| ۳ | ۱۷ | $1 \le n \le 12$ |
| ۴ | ۴۴ | $1 \le n, k \le 30$ |
| ۵ | ۲۹ | بدون محدودیت اضافی |
مثال
ورودی نمونه ۱
6 2
1 2 2 1 1 2
خروجی نمونه ۱
5
ورودی نمونه ۲
6 4
3 2 3 1 2 3
خروجی نمونه ۲
4
ارسال پاسخ برای این سؤال