نقشه‌کش دستگاهی برای چاپ گرافیکی است که برای این کار به کامپیوتر متصل می‌شود. دو نوع نقشه‌کش وجود دارد: نقشه‌کش خودکاری و نقشه‌کش الکترواستاتیکی. نقشه‌کش‌های خودکاری با حرکت دادن خودکار در سطح صفحه چاپ می‌کنند و توانایی رسم خطوط مرکب مثل متن و نوشته را دارند؛ اما به دلیل حرکت مکانیکی خودکار، این کار را بسیار آهسته انجام می‌دهند. در این مسئله ما به سرعتِ کمِ نقشه‌کشِ ویژه‌ای که داریم توجه می‌کنیم. نقشه کشِ خودکاریِ افقیِ مجزا تنها می‌تواند بازه‌های افقی‌ را که دو نقطه ابتدا و انتهای آن متمایز هستند رسم کند ($x$ و $y$ اعداد صحیح هستند). روش رسم آن کاملاً ساده است؛ خودکار از گوشه‌ی بالا چپِ صفحه ($x = y = 0$) شروع می‌کند و فقط به راست حرکت می‌کند تا در آن سطر خطوط خواسته شده را رسم کند. سپس کاملاً به چپ برمی‌گردد و یک سطر پایین می‌رود ($y ← y - 1$) و این کار را برای سطر دوم و همچنین سطر‎‌های بعدی تکرار می‌کند. در واقع خودکار تنها در صورتی که در چپ‌ترین نقطه سطر ($x = 0$) باشد می‌تواند به سطر بعد برود و در هر سطر حداکثر یک حرکت راست به چپ و حداکثر یک حرکت چپ به راست می‌تواند داشته باشد.

هر یک واحدِ حرکت به چپ ($x ← x - 1$) و راست ($x ← x + 1$) یک واحد زمانی طول می‌کشد. اگر خودکار روی صفحه باشد و یک بازه را رسم کند، این زمان دو برابر می‌شود. حرکت به سطر بعدی زمان نمی‌برد (وقتی $x = 0$).

ممکن است رسم کردن همه‌‌ی خطوط، مدت زیادی طول بکشد؛ بنابراین تصمیم گرفتیم به نقشه‌کش ویژگی جدیدی اضافه کنیم: محدودیت زمانی رسم. با مشخص کردن محدودیت زمانی، نقشه‌کش باید بیش‌ترین تعداد خطی را رسم کند که با روش توضیح داده شده در این زمان می‌توان رسم کرد. با دادن محدودیت زمانی و خط‌وط، شما باید بیش‌ترین تعداد خطی را که می‌توان رسم کرد پیدا کنید.

• فایل ورودی شامل تعدادی تست است. هر تست با خطی شامل ۲ عدد $n$ و $t$ می‌باشد. $n$ تعداد پاره‌خط‌ها ($n \leq 1000$) و $t$ حد زمانی ($t \leq 10^6$) است.
• هر یک $n$ خط بعدی یک پاره‌خط را با $y$، $x_s$ و $x_t$ نشان‌ می‌دهد. $y$ سطر شامل آن پاره‌خط را معین می‌کند ($0 \leq y \leq 2000$) و $x_s$ و $x_t$ ۲ سر آن پاره‌خط را نشان می‌دهند ($0 \leq x_s \leq x_t \leq 10^6$). پاره‌خط‌ها مجزا از هم بوده و هیچ‌گونه تلاقی ندارند.
• حالت $n = t = 0$ پایان فایل ورودی را نشان می‌دهد و جوابی برای آن نباید خروجی دهید.

به ازای هر تست، در یک خط تنها یک عدد خروجی دهید که به معنا‌ی بیش‌ترین تعداد پاره‌خط‌ها است که می‌توان رسم کرد.

• محدودیت زمان: ۱۰ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

• سوال بعد
• سوال قبل