Problem Background

Beside the pond, the banyan tree, the cicadas are chirping away the summer;
Beside the playground, the swing, only butterflies are resting on it;
On the blackboard, the teacher's chalk is still busily scratching away;
Waiting for the bell, waiting for school's end,
Waiting for the childhood of games.

Problem Description

Charlie loved climbing trees in his childhood.

One day, Charlie prepared to challenge a tall apple tree. This tree has $n$ nodes, with node $1$ being the root.

Each node may have several apples or a bird's nest. If the node has apples, Charlie will pick all of them and put them in his pocket. If the node has a bird's nest and it is Charlie's first visit to it, Charlie will give each bird in the nest an apple (don't ask why birds like apples).

Specifically, if Charlie does not have enough apples in his pocket to give one to each bird in the node, he will not go to that node. Note that when Charlie passes a node again, he will not pick apples or give apples again.

Initially, Charlie has $s$ apples in his pocket. Charlie will start climbing from the root, and each time he reaches a node through an edge, he will perform the corresponding action (pick apples or give apples, including the root node). Charlie hopes to have the maximum number of apples in the end. Since Charlie is busy climbing other trees, he wants you to write a program to help him.

Input Format

The first line contains two integers $n$ and $s$, as described above.

The next line contains $n-1$ integers, where the $i$-th integer represents the parent node $p_i$ of node $i+1$.

The following line contains $n$ integers, where the $i$-th integer $a_i$ indicates: if $a_i > 0$, the node has $a_i$ apples; if $a_i < 0$, the node has a bird's nest with $|a_i|$ birds; if $a_i = 0$, the node is empty.

Output Format

A single integer representing the maximum number of apples Charlie can have in the end.

Sample Input and Output

Sample Input #1

5 0
1 1 2 2
1 1 1 1 1

Sample Output #1

5

Sample Input #2

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

Sample Output #2

2

Sample Input #3

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

Sample Output #3

8

Notes/Hints

Sample 1 Explanation:

All apples can be picked.

Sample 2 Explanation:

Only the apples at nodes $1$ and $3$ can be picked, as node $2$ cannot be visited due to too many birds.

Sample 3 Explanation:

Node $1$ gives away $2$ apples, then picks all apples at nodes $3, 6, 7$, resulting in $6$ apples in the pocket. Then passes through node $2$, and picks the apples at node $5$. Node $4$ is not necessary to visit due to too many birds.

An optimal path: $1 \rightarrow 3 \rightarrow 6 \rightarrow 3 \rightarrow 7 \rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 5 \rightarrow 2 \rightarrow 1$.

Data Range and Constraints

This problem is bundled.

• 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): No special restrictions.

For $100\%$ of the data, $1 \leq n \leq 6000, 1 \leq p_i < i, |a_i| \leq 10^9, 0 \leq s \leq 10^9$.

见题面 Input 部分

见题面 Output 部分