Mitya 和 Vasya 正在玩一个有趣的游戏。它们有一个有 $$$n$$$ 个顶点的有根树,并且顶点的索引从 $$$1$$$ 到 $$$n$$$。根的索引为$$$1$$$。每个其他顶点 $$$i \ge 2$$$ 都有其父顶点 $$$p_i$$$,并且顶点 $$$i$$$ 称为顶点 $$$p_i$$$ 的子顶点。
树的每个顶点都有一些 cookie:顶点 $$$i$$$ 中有 $$$x_i$$$ cookie。 Mitya 恰好需要 $$$t_i$$$ 时间才能吃掉顶点 $$$i$$$ 中的一块饼干。还有一个芯片,它最初位于树的根部,需要 $$$l_i$$$ 时间来沿着连接顶点 $$$i$$$ 与其父节点的边移动芯片。
Mitya 和 Vasya 轮流演奏,Mitya 先演奏。
- Mitya 将芯片从芯片所在的顶点移动到其子项之一。
- Vasya 可以将芯片所在顶点的一条边移至其子节点之一。瓦夏也可以决定跳过他的回合。
Mitya 可以在任何回合停止游戏。一旦他停止游戏,他就会将芯片移动到根部,并沿途吃掉一些饼干。米蒂亚可以决定他想在途中的每个顶点吃多少饼干。下降、上升和吃饼干所花费的总时间不应超过$$$T$$$。请注意,在游戏结束时,芯片始终位于树的根部:Mitya 不能将芯片留在任何其他顶点,即使他已经吃掉了足够的饼干 - 他必须将芯片移回根部(从顶点 $$$v$$$ 到其父节点的每次移动都需要 $$$l_v$$$ 时间)。
找出无论 Vasya 的行为如何,Mitya 最多可以吃多少块饼干。
输入
第一行包含两个整数 $$$n$$$ 和 $$$T$$$ - 树中的顶点数和完成任务所需的时间 ($$$2\le n \le 10^5$$$; $$$1\le T\le10^{18}$$$)。
第二行包含 $$$n$$$ 整数 $$$x_1$$$, $$$x_2$$$, ..., $$$x_n$$$ - 位于相应顶点 ($$$1\le x_i\le10^6$$$) 的 cookies 数量。第三行包含 $$$n$$$ 整数 $$$t_1$$$, $$$t_2$$$, ..., $$$t_n$$$ - Mitya 在顶点 $$$i$$$ ($$$1\le t_i\le10^6$$$) 中吃掉一块饼干需要多长时间。
以下 $$$n - 1$$$ 行中的每一行都描述了该树。对于从 $$$2$$$ 到 $$$n$$$ 的每个 $$$i$$$,相应的行包含两个整数 $$$p_i$$$ 和 $$$l_i$$$,其中 $$$p_i$$$ 表示顶点 $$$i$$$ 的父节点,$$$l_i$$$ 表示 Mitya 将芯片沿边从顶点 $$$i$$$ 移动到其顶点所需的时间。父级($$$1\le p_i < i$$$,$$$0\le l_i \le 10^9$$$)。
输出
输出一个整数——Mitya 可以吃的最大饼干数量。
示例
输入 #1
5 26 1 5 1 7 7 1 3 2 2 2 1 1 1 1 2 0 2 0
输出 #1
11
输入 #2
3 179 2 2 1 6 6 6 1 3 2 3
输出 #2
4
注意
在第一个示例测试用例中,Mitya 可以首先将芯片移动到顶点 $$$2$$$。在这种情况下,无论 Vasya 玩得如何,Mitya 都能吃至少 $$$11$$$ 饼干。下面您可以找到动作的详细说明:
1. Mitya 将芯片移动到顶点 $$$2$$$。
2. Vasya 移除到顶点 $$$4$$$ 的边。
3. Mitya 将芯片移动到顶点 $$$5$$$。
4. 由于顶点 $$$5$$$ 没有子节点,因此 Vasya 不会删除任何边。
5. Mitya 停止游戏并将芯片移向根部,一路吃饼干(顶点 $$$5$$$ 中的 $$$7$$$,顶点 $$$2$$$ 中的 $$$3$$$,顶点 $$$1$$$ 中的 $$$1$$$)。
Mitya 花费 $$$1+0$$$ 时间下降,$$$0+1$$$ 上升,$$$7\cdot 2$$$ 在顶点 5 吃 $$$7$$$ 饼干,$$$3\cdot 3$$$ 在顶点 2 吃 $$$3$$$ 饼干,$$$1\cdot 1$$$ 吃顶点 1 中的 $$$1$$$ cookie。总时间为 $$$1+0+0+1+7\cdot 2+3\cdot 3+1\cdot 1=26$$$。