+ محدودیت زمان: ۱.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- فردا تولد حیدریه! حیدری در مغازه‌ش $n$ تا جنس برای فروش دارد و می‌خواهد به مناسبت تولدش جشنواره تخفیف برگزار کند. جشنواره حیدری به این صورت است که او یک زیرمجموعه از اجناس مغازه‌اش و یک عدد $X$ را اعلام می‌کند. سپس مشتری‌ها این اجناس را می‌خرند. اگر مشتری‌ای دقیقاً ۲ تا از اجناس آن زیر مجموعه را بخرد و جمع قیمت آن‌ها اکیداً بیش‌تر از $X$ باشد، آن مشتری تخفیف می‌گیرد. از آن‌جا که حیدری از تخفیف دادن متنفر است به او کمک کنید اندازه بزرگترین زیر مجموعه‌ای را برای جشنواره پیدا کند که کسی نتواند از او تخفیف بگیرد. # ورودی در خط اول ورودی دو عدد طبیعی $n$ و $X$ با فاصله از هم آمده است. سپس در خط دوم ورودی $n$ عدد آمده است که قیمت هر یک از اجناس مغازه را نشان می‌دهد. قیمت هر جنس حداکثر $10^9$ تومان است. $$1 \le n \le 100\ 000$$ $$1 \le X \le 10^9$$ # خروجی در خروجی یک عدد چاپ کنید که نشان دهنده بیش‌ترین تعداد اجناسیست که حیدری می‌تواند برای جشنواره انتخاب کند به صورتی که کسی نتواند از او تخفیف بگیرد. # مثال ## ورودی نمونه ۱ ``` 5 6 1 2 3 4 5 ``` ## خروجی نمونه ۱ ``` 3 ``` ## ورودی نمونه ۲ ``` 5 10 4 8 1 9 7 ``` ## خروجی نمونه ۲ ``` 2 ``` ## ورودی نمونه ۳ ``` 4 10 1 3 1 7 ``` ## خروجی نمونه ۳ ``` 4 ``` ## ورودی نمونه ۴ ``` 1 5 6 ``` ## خروجی نمونه ۴ ``` 1 ``` ---------- <details class="orange"> <summary> راهنمایی ۱ </summary> همیشه بهترین حالت این است که اگر جواب سوال $k$ باشد، حیدری $k$ جنس با کم‌ترین قیمت را انتخاب کند. پس برای یافتن بهترین جواب، قیمت اجناس را به صورت صعودی مرتب می‌کنیم و سپس از ابتدا تا جایی پیش می‌رویم که جمع قیمت ۲ جنس با بیش‌ترین قیمت از $X$ کم‌تر باشد. در راهنمایی بعدی شبه کد روند یافتن جواب بیشتر توضیح داده می‌شود. </details> <details class="orange"> <summary> راهنمایی ۲ </summary> خب حالا ابتدا باید قیمت‌ها را به صورت صعودی مرتب کنیم سپس جواب را پیدا کنیم، برای این کار به روش زیر عمل می‌کنیم! ```c sort(prices) ans = n for i in 2 -> n: if prices[i] + prices[i - 1] > X: ans = i - 1 break ``` </details>

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