eolymp
bolt
Try our new interface for solving problems
Məsələlər

G. Команда

G. Команда

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Козак Вус хоче провести спецоперац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.

Giriş verilənləri

Перший рядок м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дерства.

Çıxış verilənləri

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

####Примiтка

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

Nümunə

Giriş verilənləri #1
5 4
0 3 3
1 3 5
2 2 2
1 2 4
2 3 1
Çıxış verilənləri #1
6
Mənbə 2019-2020 ACM-ICPC, SEERC, 1/4 фiналу, Днiпро, Київ, Львiв, Миколаїв, Тернопiль, Харкiв, 14 вересня 2019