Festive Baobab

Do you know where the baobab is in the Math&Mech building? If not, ask someone after the contest to show you...

Everyone knows the baobab is a tree. Like any tree, it has a trunk and branches. Branches grow from the trunk or from other branches.

On September 1, the baobab is usually decorated to make new students feel comfortable. For this purpose, a large chest with small colorful decorations sits deep in the building's dungeons. Every decoration weighs exactly one gram.

Unfortunately, the baobab is very old, so it breaks if overloaded with decorations. For each branch, you know the maximum weight of decorations it can carry. If a branch, together with all branches growing from it (directly or through other branches), carries decorations whose total weight exceeds this limit, the branch breaks. This is unacceptable. But you can put several decorations on a single branch, as long as it does not cause any branch to break.

Some branches are near the entrance and clearly visible, while others are hidden in the depths of the baobab. So each decoration brings more or less joy depending on its position. The total joy of the baobab is the sum of the joys of the branches where decorations are located. If several decorations are on a single branch, that branch's joy is multiplied by their quantity.

What is the maximum possible total joy the baobab can have?

The first line contains two integers $n$ and $t$: the number of branches on the baobab and the number of decorations ($1 \le n \le 100\,000$, $1 \le t \le 10^9$). Each of the next $n$ lines contains three integers $d_i$, $p_i$, and $w_i$: the joy a single decoration on the $i$-th branch gives, the branch that the $i$-th branch grows from (or $0$ if the $i$-th branch grows directly from the trunk), and the maximum weight of decorations the $i$-th branch can carry ($1 \le d_i, w_i \le 10^9$, $0 \le p_i \le n$).

Every branch grows from the trunk, directly or through other branches. It is also guaranteed that it is possible to use all decorations.

Output one integer: the maximum total joy the decorated baobab gives.