题目描述

小 T 与小 L 终于决定走在一起,他们不想浪费在一起的每一分每一秒,所以他们决定每天早上一同晨练来享受在一起的时光。

他们画出了晨练路线的草图,眼尖的小 T 发现可以用树来描绘这个草图。

他们不愿枯燥的每天从同一个地方开始他们的锻炼,所以他们准备给起点标号后顺序地从每个起点开始(第一天从起点一开始,第二天从起点二开始......)。而且他们给每条道路定上一个幸福的值.很显然他们每次出发都想走幸福值和最长的路线(即从起点到树上的某一点路径中最长的一条)。

他们不愿再经历之前的大起大落,所以决定连续几天的幸福值波动不能超过 $M$ (即一段连续的区间并且区间的最大值最小值之差不超过 $M$ )。他们想知道要是这样的话他们最多能连续锻炼多少天 ( hint : 不一定从第一天一直开始连续锻炼 ) ?

现在，他们把这个艰巨的任务交给你了!

输入格式

第一行包含两个整数 $N, M$ ( $M \le 10^9$ )。

第二至第 $N$ 行,每行两个数字 $F_i$ , $D_i$ 。

第 $i$行表示第 $i$ 个节点的父亲是 $F_i$ ,且道路的幸福值是 $D_i$ 。

输出格式

最长的连续锻炼天数。

3 2
1 1
1 3

3

数据范围：

50% 的数据 $N \le 10^3$

80% 的数据 $N \le 10^5$

100% 的数据 $N \le 10^6$