G. Команда
Козак Вус хоче провести спецоперацiю. Його армiя має жорстку iєрархiю. Сам Вус — Верховний головнокомандувач, йому пiдпорядкуються генерали, яким пiдпорядкуються полковники, i так далi.
Якщо одна людина має безпосереднього керiвника, то її керiвником вважається i керiвник безпосереднього керiвника, i його безпосереднiй керiвник, i так далi. Кожен вiйськовий p має фiксовану зарплатню c[p] гривень (дивно, але iнодi керiвники отримують менше за пiдпорядкованих).
Загальний бюджет на загiн становить b гривень. Загiн складається з керiвника та виконавцiв. Козак Вус може назначити керiвником як себе, так i будь-якого iншого солдата. А виконавцями можуть бути лише пiдпорядкованi керiвниковi (включаючи його самого) солдати, хоча керiвник незобов’язаний бути також i виконавцем. Рiвень загону — це добуток рiвня лiдерства l керiвника та кiлькостi виконавцiв.
Допоможiть Козаковi Вусу знайти найбiльший можливий рiвень загону, заплативши кожному виконавцю так, щоб сумарнi витрати не перевищували b.
Вхідні дані
Перший рядок мiстить два цiлi числа n та b (1 ≤ n ≤ 100 000, 1 ≤ b ≤ 1 000 000 000) — кiлькiсть солдатiв та бюджет операцiї.
Наступнi n рядкiв мiстять три цiлi числа 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) — безпосереднiй керiвник вiйськового, або 0, якщо це Козак Вус, зарплатня та рiвень лiдерства.
Вихідні дані
В єдиному рядку виведiть вiдповiдь на задачу
####Примiтка
Найкращим варiантом буде вибрати керiвником вiйськового пiд номером 1 (Козака Вуса) та вибрати виконавцями вiйськових пiд номерами 3 та 4.