- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
پس از یک حادثه در خلیج مهآلود \(n\) نفر باید با قایقهای نجات به ساحل منتقل شوند. هر نفر وزن مشخصی دارد. هر قایق ظرفیت تحمل وزن \(w\) دارد و در هر قایق حداکثر دو نفر میتوانند سوار شوند.
برای کاهش زمان عملیات، فرمانده گفته باید با کمترین تعداد قایق همه افراد منتقل شوند. اگر دو نفر در یک قایق باشند، مجموع وزنشان باید حداکثر \(w\) باشد.
به شما تعداد افراد \(n\)، ظرفیت قایق \(w\) و وزن هر فرد داده میشود. در هر قایق حداکثر 2 نفر میتوانند سوار شوند و مجموع وزن آنها نباید از \(w\) بیشتر شود. همچنین تضمین می شود که وزن هر فرد در بازه بین \(1\) تا \(w\) می باشد.
کمترین تعداد قایق لازم برای انتقال همه افراد را چاپ کنید.
ورودی
در خط اول ورودی دو عدد \(n\) و \(w\) میآید و سپس در خط دوم \(n\) عدد صحیح با فاصله میآید که نشاندهنده وزن افراد می باشد
\[ 1 \le n \le 2 \cdot 10^5 \] \[ 1 \le w \le 10^9 \]
خروجی
در تنها خط خروجی یک عدد برابر کمینه تعداد قایق مورد نیاز چاپ کنید.
مثال
ورودی
4 10
7 2 3 9
خروجی
3
ورودی
6 7
1 2 3 4 5 6
خروجی
3