레이팅 미적용Freyr, the god of prosperity, rain and the harvest, is having a lot of trouble these days. The giants are once again trying to invade Midgard, and have built a war camp at the bottom of the many valleys leading to Midgard. Now Freyr needs to wash that camp away, so a great victory feast can be held. Being at the bottom of the valley, any rain in the region can make its way through rivers and streams to the bottom of the valley and contribute to the glorious flooding of the giants. However, beavers and industrious humans have built dams throughout the river system, and these act as buffers that can hold some amount of water. But, on the flip side, once a dam is filled up to its capacity, it will break and all of the water stored there (as well as any further water added) will be released downstream.
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 for an example.
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 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