G. Команда

Казак Вус планирует провести спецоперацию, для которой его армия, обладающая строгой иерархией, должна быть организована оптимальным образом. В этой иерархии Вус занимает позицию Верховного главнокомандующего. Ему подчиняются генералы, генералам — полковники, и так далее.

Если у человека есть непосредственный начальник, то начальниками считаются также начальники его начальника и так далее вверх по иерархии. Каждый военный p получает фиксированную зарплату c[p] гривен (что может быть неожиданно, но иногда начальники получают меньше своих подчиненных).

Общий бюджет операции составляет b гривен. Отряд состоит из руководителя и исполнителей. Казак Вус может назначить руководителем как себя, так и любого другого солдата. Исполнителями могут быть только подчиненные руководителю (включая его самого) солдаты, хотя руководитель не обязан быть исполнителем. Уровень отряда определяется как произведение уровня лидерства l руководителя и количества исполнителей.

Ваша задача — помочь Казаку Вусу определить максимальный возможный уровень отряда, при этом выплачивая каждому исполнителю зарплату так, чтобы общие расходы не превышали b.

Формат входных данных

Первая строка содержит два целых числа n и b (1 ≤ n ≤ 100 000, 1 ≤ b ≤ 1 000 000 000) — количество солдат и бюджет операции.

Следующие n строк содержат три целых числа p[i], c[i], l[i] (1 ≤ p[i] ≤ i − 1, p[i] = 0, если i = 1, 1 ≤ c[i], l[i] ≤ 1 000 000 000) — непосредственный начальник военного, или 0, если это Казак Вус, зарплата и уровень лидерства.

Формат выходных данных

Выведите в единственной строке максимальный возможный уровень отряда.

Примеры

Примечание

Наилучший вариант — выбрать руководителем военного под номером 1 (Казака Вуса) и назначить исполнителями военных под номерами 3 и 4.