Диспетчер
В клане ниндзя, ниндзя отправляют к клиенту, и потом они получают вознаграждение в соответствии с их работой.
В клане ниндзя имеется один ниндзя, именуемый Мастером. Каждый ниндзя кроме Мастера имеет ровно одного босса. Чтобы гарантировать конфиденциальность и поощрить лидерство, все инструкции по заданиям всегда передаются боссом своим подчинённым. Другими методами запрещается передавать инструкции.
Вы хотите собрать некоторое количество ниндзя и отправить их к клиенту. Вы должны заплатить каждому из отправленных ниндзя. Для каждого ниндзя зафиксирована оплата. Суммарная плата должна уложится в бюджет. Кроме того, чтобы передавать инструкции отправленным ниндзя, Вы должны выбрать одного ниндзя как менеджера, который сможет посылать инструкции всем им. Ниндзя, который не был выбран, может передавать сообщения. Менеджер не обязательно должен быть отправлен к клиенту. Если менеджер не отправлен, ему не нужно платить.
Вы хотите максимизировать степень удовлетворённости клиента, оставаясь в рамках бюджета. Степень удовлетворённости вычисляется как произведение общего количества отправленных ниндзя и уровня лидерства менеджера. Для каждого ниндзя обозначен его уровень лидерства.
Напишите программу, которая зная для каждого ниндзя его босса b[i], размер оплаты c[i], уровень лидерства l[i] (1 ≤ i ≤ n), и размер бюджета m, выведет максимально возможное значение уровня удовлетворённости клиента, при условии, что менеджер и отправленные ниндзя выбраны так, что все условия соблюдены.
Входные данные
Первая строка содержит количество ниндзя n (1 ≤ n ≤ 10^5) и бюджет m (1 ≤ m ≤ 10^9). Следующие n строк описывают босса, зарплату и уровень лидерства каждого ниндзя. (i + 1) - ая строка содержит три целых числа b[i], c[i], l[i] (0 ≤ b[i] < i, 1 ≤ c[i] ≤ m, 1 ≤ l[i] ≤ 10^9), обозначающих босса i-го ниндзя b[i], зарплату i-го ниндзя c[i], и его лидерский уровень l[i]. i-ый ниндзя является Мастером, если b[i] = 0. Так как всегда соблюдается неравенство b[i] < i, то для каждого ниндзя номер его босса всегда меньше номера его самого.
Выходные данные
Выведите максимальное возможное значение уровня удовлетворённости клиента.
Примечание к примеру
Если выбрать ниндзя 1 менеджером и отправить к клиенту ниндзя 3, 4, то общая оплата будет равна 4 и не превысит бюджет. Так как количество отправленных ниндзя 2 и лидерский уровень менеджера 3, то уровень удовлетворённости клиента 6. Это максимально возможное значение.