+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت + منبع: آزمون نهایی اول دوره ۲۷ المپیاد کامپیوتر ---------- السا و مهرسا می‌خواهند میوه‌ها را برای مراسم آماده کنند. السا وظیفه شستن میوه‌ها را بر‌عهده دارد و مهرسا باید میوه‌ها را در ظرف قرار دهد. $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 ```