「EVOI-RD2」童年

池塘边的榕树上 知了在声声地叫着夏天 操场边的秋千上 只有蝴蝶儿停在上面 黑板上老师的粉笔还在拼命叽叽喳喳写个不停 等待着下课 等待着放学 等待游戏的童年

Charlie 童年时代很喜欢爬树。 有一天，Charlie 准备向一棵高大的苹果树发起挑战。这棵苹果树有 $n$ 个结点，其中结点 $1$ 为树根。 每个结点会有若干个苹果或一个鸟巢。若这个结点上是若干个苹果，则 Charlie 会摘下所有的苹果装入自己的口袋中；若这个结点是鸟巢**且 Charlie 是第一次访问它**，则 Charlie 会给这个鸟巢中的每只鸟儿一个苹果~~不要问鸟儿为什么喜欢苹果~~。 特别地，如果 Charlie 当前口袋中的苹果不足以给该结点的每只鸟儿一个，则他就不会走向这个结点。注意 Charlie 重复经过一个结点时，不会重复采摘苹果，也不会重复给出苹果。 一开始，Charlie 口袋中有 $s$ 个苹果。Charlie 将从树根开始爬树，每次经过一条边到达一个结点，并执行对应的操作（摘苹果或给苹果，根结点的操作也要执行）。Charlie 希望最终拥有的苹果数最多。由于 Charlie 还在忙着爬其他的树，他想请你写个程序帮帮他。

第一行两个整数 $n,s$，含义如上所示。 接下来一行 $n-1$ 个整数，第 $i$ 个整数代表第 $i+1$ 号结点的父亲 $p_i$。 再接下来一行 $n$ 个整数，第 $i$ 个数为 $a_i$。若 $a_i>0$，则代表这个结点有 $a_i$ 个苹果；若 $a_i<0$，则代表这个结点有一个 $|a_i|$ 只鸟儿的鸟巢；若 $a_i=0$，则说明这个结点什么也没有。

一行一个整数，代表 Charlie 最终拥有的最多苹果数。

5 0
1 1 2 2
1 1 1 1 1

5

5 0
1 1 2 2
1 -3 1 2 2

2

8 5
1 1 2 2 3 3 4
-2 -6 1 -7 8 1 1 6

8

**样例 1 解释：** 可以摘走所有苹果。 **样例 2 解释：** 只能摘走结点 $1,3$ 的苹果，结点 $2$ 因为鸟儿太多无法访问。 **样例 3 解释：**  结点 $1$ 给掉 $2$ 个苹果，先摘完结点 $3,6,7$ 的苹果，此时口袋中有 $6$ 个苹果。再闯过结点 $2$，然后拿走结点 $5$ 的苹果，结点 $4$ 由于鸟儿太多没必要走。 一种最优的具体路径：$1 \rightarrow 3 \rightarrow 6 \rightarrow 3 \rightarrow 7 \rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 5 \rightarrow 2 \rightarrow 1$。 **数据规模与约定** **本题采用捆绑测试。** + Subtask 1 (10 pts)：$\, n \leq 10$。 + Subtask 2 (20 pts)：$\, n \leq 100$ 。 + Subtask 3 (10 pts)：$\, p_i=1$。 + Subtask 4 (30 pts)：$\, p_i=i-1$。 + Subtask 5 (30 pts)：无特殊限制。 对于 $100\%$ 的数据，$1 \leq n \leq 6000, 1 \leq p_i \lt i, |a_i| \leq 10^9,0 \leq s \leq 10^9$。 --- “记得门前，有两株树，一株是苹果树，还有一株……也是苹果树。”