Диспетчер#3384
У клані ніндзя, ніндзя відправляють до клієнта, і потім вони отримують винагороду відповідно до їхньої роботи.
У клані ніндзя є один ніндзя, якого називають Майстром. Кожен ніндзя, окрім Майстра, має рівно одного боса. Щоб гарантувати конфіденційність і заохотити лідерство, всі інструкції щодо завдань завжди передаються босом своїм підлеглим. Інші методи передачі інструкцій заборонені.
Ви хочете зібрати певну кількість ніндзя і відправити їх до клієнта. Ви повинні заплатити кожному з відправлених ніндзя. Для кожного ніндзя зафіксована оплата. Сумарна плата повинна вкластися в бюджет. Крім того, щоб передавати інструкції відправленим ніндзя, Ви повинні обрати одного ніндзя як менеджера, який зможе надсилати інструкції всім їм. Ніндзя, який не був обраний, може передавати повідомлення. Менеджер не обов'язково повинен бути відправлений до клієнта. Якщо менеджер не відправлений, йому не потрібно платити.
Ви хочете максимізувати ступінь задоволеності клієнта, залишаючись у межах бюджету. Ступінь задоволеності обчислюється як добуток загальної кількості відправлених ніндзя і рівня лідерства менеджера. Для кожного ніндзя позначено його рівень лідерства.
Напишіть програму, яка знаючи для кожного ніндзя його боса b_i, розмір оплати c_i, рівень лідерства l_i (1 \leq i \leq n), і розмір бюджету , виведе максимально можливе значення рівня задоволеності клієнта, за умови, що менеджер і відправлені ніндзя обрані так, що всі умови дотримані.
Перший рядок містить кількість ніндзя (1 \leq n \leq 10^5) і бюджет (1 \leq m \leq 10^9). Наступні рядків описують боса, зарплату і рівень лідерства кожного ніндзя. (i + 1)-ий рядок містить три цілих числа b_i, c_i, l_i (0 \leq b_i < i, 1 \leq c_i \leq m, 1 \leq l_i \leq 10^9), що позначають боса -го ніндзя b_i, зарплату -го ніндзя c_i, і його лідерський рівень l_i. -ий ніндзя є Майстром, якщо b_i = 0. Оскільки завжди виконується нерівність b_i < i, то для кожного ніндзя номер його боса завжди менший за номер його самого.
Виведіть максимально можливе значення рівня задоволеності клієнта.
Приклад 1
Якщо обрати ніндзя менеджером і відправити до клієнта ніндзя , , то загальна оплата буде дорівнювати і не перевищить бюджет. Оскільки кількість відправлених ніндзя і лідерський рівень менеджера , то рівень задоволеності клієнта . Це максимально можливе значення.