G. Команда#9092

G. Команда

1 секунда

64 мегабайти

Легка

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

Якщо одна людина має безпосереднього керівника, то її керівником вважається і керівник безпосереднього керівника, і його безпосередній керівник, і так далі. Кожен військовий $p$ має фіксовану зарплатню $c_{p}$ c_p гривень (дивно, але іноді керівники отримують менше за підпорядкованих).

Загальний бюджет на загін становить $b$ гривень. Загін складається з керівника та виконавців. Козак Вус може назначити керівником як себе, так і будь-якого іншого солдата. А виконавцями можуть бути лише підпорядковані керівникові (включаючи його самого) солдати, хоча керівник не зобов'язаний бути також і виконавцем. Рівень загону — це добуток рівня лідерства $l$ керівника та кількості виконавців.

Допоможіть Козакові Вусу знайти найбільший можливий рівень загону, заплативши кожному виконавцю так, щоб сумарні витрати не перевищували $b$ .

Вхідні дані

Перший рядок містить два цілі числа $n$ та $b$ ( $1 \leq n \leq 100000$ 1 \leq n \leq 100\,000, $1 \leq b \leq 1000000000$ 1 \leq b \leq 1\,000\,000\,000) — кількість солдатів та бюджет операції.

Наступні $n$ рядків містять три цілі числа $p_{i}$ p_i, $c_{i}$ c_i, $l_{i}$ l_i ( $1 \leq p_{i} \leq i - 1$ 1 \leq p_i \leq i - 1, $p_{i} = 0$ p_i = 0, якщо $i = 1$ i = 1, $1 \leq c_{i}, l_{i} \leq 1000000000$ 1 \leq c_i, l_i \leq 1\,000\,000\,000) — безпосередній керівник військового, або $0$ , якщо це Козак Вус, зарплатня та рівень лідерства.

Вихідні дані

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

Приклади

Приклад 1

Примітка

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