Козак Вус хоче провести спецоперацiю. Його армiя має жорстку iєрархiю. Сам Вус — Верховний головнокомандувач, йому пiдпорядкуються генерали, яким пiдпорядкуються полковники, i так далi.

Якщо одна людина має безпосереднього керiвника, то її керiвником вважається i керiвник безпосереднього керiвника, i його безпосереднiй керiвник, i так далi. Кожен вiйськовий p має фiксовану зарплатню cp гривень (дивно, але 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лi числа n та b (**1 ≤ n ≤ 100 000, 1 ≤ b ≤ 1 000 000 000**) — кiлькiсть солдатiв та бюджет операцiї.

Наступнi n рядкiв мiстять три цiлi числа pi, ci , li (**1 ≤ pi ≤ i − 1, pi = 0**, якщо i = 1, 1 ≤ ci, li ≤ 1 000 000 000) — безпосереднiй керiвник вiйськового, або 0, якщо це Козак Вус, зарплатня та рiвень лiдерства.

Формат вихiдних даних

В єдиному рядку виведiть вiдповiдь на задачу

Примiтка

Найкращим варiантом буде вибрати керiвником вiйськового пiд номером 1 (Козака Вуса) та вибрати виконавцями вiйськових пiд номерами 3 та 4.