Background

On the banyan tree by the pond, cicadas keep calling out summer.
On the swing by the playground, only butterflies rest on it.
On the blackboard, the teacher’s chalk keeps squeaking and writing nonstop.
Waiting for the bell, waiting for school to end.
Waiting for a childhood of games.

Problem Description

Charlie loved climbing trees when he was a child.

One day, Charlie decided to challenge a tall apple tree. This apple tree has $n$ nodes, where node $1$ is the root.

Each node contains either some apples or one bird nest. If the node has some apples, Charlie will pick all the apples and put them into his pocket. If the node is a bird nest and Charlie visits it for the first time, then Charlie will give one apple to each bird in the nest don’t ask why birds like apples.

In particular, if Charlie does not have enough apples in his pocket to give one to every bird at that node, then he will not go to that node. Note that when Charlie passes through a node multiple times, he will not pick apples again, and he will not give apples again.

Initially, Charlie has $s$ apples in his pocket. Charlie will start climbing from the root. Each time he passes along an edge to reach a node, he performs the corresponding operation (picking apples or giving apples; the operation at the root also counts). Charlie wants to maximize the number of apples he has in the end. Since Charlie is busy climbing other trees, he asks you to write a program to help him.

Input Format

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

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

The next line contains $n$ integers. The $i$-th number is $a_i$. If $a_i > 0$, then this node has $a_i$ apples. If $a_i < 0$, then this node has a bird nest with $|a_i|$ birds. If $a_i = 0$, then this node has nothing.

Output Format

Output one integer in one line, representing the maximum number of apples Charlie can have in the end.

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

Hint

Explanation for Sample 1:

All apples can be picked.

Explanation for Sample 2:

Only the apples at nodes $1$ and $3$ can be picked. Node $2$ cannot be visited because there are too many birds.

Explanation for Sample 3:

At node $1$, Charlie gives away $2$ apples. First, he picks all apples at nodes $3, 6, 7$, and now he has $6$ apples in his pocket. Then he passes through node $2$, and takes the apples at node $5$. Node $4$ is not worth visiting because there are too many birds.

One optimal specific path is: $1 \rightarrow 3 \rightarrow 6 \rightarrow 3 \rightarrow 7 \rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 5 \rightarrow 2 \rightarrow 1$.

Constraints and Notes

This problem uses bundled testdata.

• 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 testdata, $1 \leq n \leq 6000$, $1 \leq p_i \lt i$, $|a_i| \leq 10^9$, and $0 \leq s \leq 10^9$.

“Do you remember? In front of the door, there were two trees. One was an apple tree, and the other one... was also an apple tree.”

Translated by ChatGPT 5