丰饶、雨水与丰收之神弗雷（Freyr）最近遇到了大麻烦。巨人们再次试图入侵米德加尔特（Midgard），并在通往米德加尔特的许多山谷底部建立了战争营地。现在，弗雷需要将那个营地冲走，以便举行盛大的胜利庆典。由于营地位于山谷底部，该地区的任何降雨都可以通过河流和溪流汇集到山谷底部，从而为冲垮巨人营地做出贡献。然而，海狸和勤劳的人类在整个河流系统中建造了许多水坝，这些水坝充当了缓冲器，可以储存一定量的水。但另一方面，一旦水坝被填满至其容量，它就会决堤，所有储存的水（以及随后添加的任何水）都会被释放到下游。

作为雨神，弗雷确切地知道需要多少水才能冲走战争营地，并且对于每一座水坝，他都知道其确切的容量以及当前储存了多少水。弗雷同时也是丰饶与丰收之神，他还有更重要的事情要做，而不是整天到处降雨，因此弗雷决定只在一个地方（水坝或战争营地）降雨，并尽可能减少在该地点的降雨量。在精心选择降雨地点的条件下，弗雷为了冲走巨人的战争营地，最少需要降多少雨？

水坝网络和战争营地构成了一棵有根树，其中战争营地是根，水坝的父节点是该水坝下游紧邻的位置（可能是另一座水坝，也可能是战争营地）。参见图 2 获取示例。

图 2：样例输入 1 的说明。在这种情况下，弗雷只需在最左侧的水坝处降下 2 单位的雨，就能使其决堤并向下游输送 50 单位的水，最终导致 100 单位的水到达战争营地，远超冲垮营地所需的 75 单位水。

输入格式

第一行包含两个整数 $n$ 和 $w$ ($1 \le n \le 2 \cdot 10^5$, $1 \le w \le 10^9$)，分别表示水坝的数量和冲走战争营地所需的水量。接下来 $n$ 行，描述这 $n$ 座水坝。水坝编号从 $1$ 到 $n$。

第 $i$ 行包含三个整数 $d_i$、$c_i$ 和 $u_i$ ($0 \le d_i < i$, $1 \le c_i \le 10^9$, $0 \le u_i < c_i$)，其中 $d_i$ 是水坝 $i$ 下游紧邻的水坝编号（如果战争营地紧邻水坝 $i$ 的下游，则为 $0$），$c_i$ 是水坝 $i$ 的最大容量，$u_i$ 是水坝 $i$ 当前的水量。

输出格式

输出弗雷在一个地点降雨所需的最少雨量，该降雨量将导致至少 $w$ 的水量到达战争营地。

样例

样例输入 1

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

样例输出 1

2

样例输入 2

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

样例输出 2

10

样例输入 3

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

样例输出 3

1