در یک فرقه‌ی نینجا‌یی، نینجاها برای خدمت‌رسانی به مشتری‌ها اعزام می‌شوند، و بر اساس کارشان جایزه می‌گیرند. در این فرقه یک نینجا وجود دارد که «استاد» نام دارد. هر نینجا به‌غیر از استاد، یک و فقط یک «رئیس» دارد. جهت رازداری و تشویق مدیریت، هر دستورالعمل مرتبط با کارشان همیشه از یک رئیس به زیردستانش ارسال می‌شود. ارسال دستورالعمل‌ها با روش‌های دیگر ممنوع می‌باشد.

شما در حال جمع‌آوری تعدادی نینجا و اعزام‌شان برای یک مشتری هستید. باید به نینجا‌های اعزام‌شده حقوق پرداخت کنید. میزان حقوق برای هر نینجا مقدار ثابت مشخصی است. جمع کل حقوق‌هایی که به نینجاهای اعزام‌شده پرداخت می‌شود، باید در حد کل بودجه‌تان باشد (نباید از کل بودجه‌تان بیشتر شود). علاوه‌برآن، برای ارسال دستورالعمل‌ها، باید نینجایی را به عنوان «مدیر» انتخاب کنید که بتواند به همه‌ی نینجاهای اعزام‌شده دستورالعمل ارسال کند. وقتی دستورالعملی ارسال می‌شود، یک نینجای اعزام‌نشده نیز می‌تواند در فرآیند انتقال دستورالعمل واسطه باشد. خود مدیر می‌تواند اعزام بشود یا نشود. اگر اعزام نشود، به او حقوق داده نخواهد شد.

شما دوست دارید سطح رضایت مشتری را تا جای ممکن در حد بودجه‌تان بیشینه کنید. سطح رضایت مشتری از حاصل‌ضرب تعداد کل نینجا‌های اعزام‌شده در عدد «سطح توانایی رهبری»ِ «مدیر» به‌دست می‌آید. عدد سطح توانایی رهبری هر نینجا نیز مقدار ثابت مشخص‌شده‌ای می‌باشد.

برنامه‌ای بنویسید که برای هر نینجای با شماره‌ی $i$ ($1 \leq i \leq N$)، شماره‌ی رئیسش $B_i$، حقوق دریافتی‌اش $C_i$، و عدد سطح توانایی رهبری‌اش $L_i$ را به همراه کل بودجه‌ی موجودی $M$ از ورودی بگیرد، و بیش‌ترین مقدار ممکن سطح رضایت مشتری را در زمانی خروجی می‌دهد که مدیر و نینجاهای اعزامی با رعایت همه‌ی شرایط مسئله انتخاب شده باشند.

• خط اول ورودی شامل دو عدد صحیح $N$ و $M$ با فاصله از هم می‌باشد که $N$ تعداد کل نینجاها و $M$ بودجه‌ی کل است.
• در $N$ خط بعد، رئیس، حقوق، و سطح توانایی هر نینجا را مشخص آمده است.
  • خط $i+1$اُمِ ورودی، شامل سه عدد صحیح $B_i$، $C_i$ و $L_i$ با فاصله از هم می‌باشد که رئیس نینجای شماره‌ی $i$، حقوق دریافتی‌اش، و عدد سطح توانایی رهبری‌اش را نشان می‌دهند. اگر $B_i=0$، نینجای $i$اُم استاد است. چون نامساوی $B_i<i$ همیشه برقرار است، شماره‌ی رئیس هر نینجا همیشه کم‌تر از شماره‌ی خودش است.
• تعداد نینجاها $ 1\leq N\leq 10^5$
• کل موجودی بودجه $1\leq M \leq 10^9$
• شماره‌ی رئیس هر نینجا $0\leq B_i<i$
• میزان حقوق هر نینجا $1 \leq C_i \leq M$
• عدد سطح توانایی رهبری هر نینجا $1\leq L_i \leq 10^9$
• در $30$ درصد تست‌ها $N\leq 3000$ می‌باشد.

بیشترین مقدار ممکن سطح رضایت مشتری را در خروجی استاندارد بنویسید.

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

در نمونه‌ی فوق، اگر ما نینجای ۱ را به عنوان مدیر و نینجاهای ۳ و ۴ را به‌عنوان نینجاهای اعزامی انتخاب کنیم، مقدار کل حقوق‌ها ۴ می‌شود که از بودجه‌ی موجود که ۴ است بیش‌تر نمی‌شود. چون تعداد نینجاهای اعزامی ۲، و عدد سطح توانایی رهبری مدیر ۳ است، سطح رضایت مشتری ۶ می‌شود. و این بیش‌ترین مقدار ممکن است.

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