Problem D
Dams in Distress

Freyr by Johannes Gehrts (1901), Public Domain

Freyr, being the god of rain, knows exactly how much water is needed to wash the war camp away, and for each dam knows its exact capacity and how much water is currently stored there. Freyr, also being the god of prosperity and harvest, has better things to do than making it rain everywhere all day, so Freyr decides to only make it rain at a single place (either a dam, or the war camp), and to make it rain as little as possible in that place. What is the minimum amount of rain that Freyr needs to make to wash away the giants war camp, provided he carefully chooses the best location for the rain?

The network of dams and the war camp form a rooted tree, where the war camp is the root and the parent of a dam is the location (either another dam, or the war camp) immediately downstream of the dam. See Figure 1 for an example.

Figure 1: Illustration of Sample Input 1. In this case Freyr only has to make $2$ units of rain at the left-most dam in order to make it break and send $50$ units of water downstream, which then ultimately results in $100$ units of rain reaching the war camp, well exceeding the $75$ units of water needed to flood the camp.

Input

The first line of input consists of two integers $n$ and $w$ ($1 \le n \le 2 \cdot 10^5$, $1 \le w \le 10^9$), the number of dams and the amount of water needed to wash away the war camp, respectively. Then follow $n$ lines, describing the $n$ dams. The dams are numbered from $1$ to $n$.

The $i$th line contains three integers $d_ i$, $c_ i$ and $u_ i$ ($0 \le d_ i < i$, $1 \le c_ i \le 10^9$, $0 \le u_ i < c_ i$), where $d_ i$ is the number of the dam immediately downstream of dam $i$ (or $0$ if the war camp is immediately downstream of dam $i$), $c_ i$ is the maximum capacity of dam $i$, and $u_ i$ is the current amount of water in dam $i$.

Output

Output the minimum amount of rain Freyr needs to make at one location, which will result in at least $w$ water reaching the war camp.

4 75
0 100 50
1 49 10
1 50 0
3 50 48

2

4 13
0 12 1
1 6 1
2 4 1
3 10 0

10

4 1
0 100 50
1 49 10
1 50 0
3 50 48

1