Problem Description

There is a gummy candy $ G $ in the shape of a rooted tree with $ N $ vertices and $ N-1 $ edges.

The vertices are numbered from $ 0 $ to $ N-1 $, and the edges are numbered from $ 1 $ to $ N-1 $.

The root is vertex $ 0 $. Edge $ i $ is an undirected edge connecting vertex $ i $ and vertex $ p_i $, with hardness $ H_i $.

You are trying to increase the number of connected components in this gummy $ G $ by repeating the following operation:

• Choose one vertex $ X $ other than the root $ 0 $ and pull the root $ 0 $ and $ X $ with both hands.
• The hardness of all edges on the path connecting the root $ 0 $ and $ X $ decreases by $ 1 $.
• All edges whose hardness becomes $ 0 $ break and disappear.
• Vertices that become disconnected from the root can no longer be chosen.

Find the maximum number of connected components of $ G $ after repeating the operations.

Input Format

The input is given from the standard input in the following format:

$ N $ $ p_1 $ $ H_1 $ $ p_2 $ $ H_2 $ $ : $ $ p_{N-1} $ $ H_{N-1} $

Output Format

Output the maximum number of connected components of $ G $ after repeating the operations.

Sample Input and Output

Sample Input #1

3
0 10
1 20

Sample Output #1

2

Sample Input #2

5
0 5
1 10
1 3
2 2

Sample Output #2

4

Sample Input #3

10
0 12
1 6
1 3
1 6
3 7
4 2
4 8
5 5
5 1

Sample Output #3

6

Notes/Hints

Constraints

• $2 \le N \le 5000$
• $0 \le p_i$
• $1 \le H_i \le 10^9$
• All inputs are integers.

Partial Points

This problem has partial points.

• Correctly solving the input with $N \le 300$ will earn you $ 500 $ points.

Sample Explanation 1

By choosing vertex $ 1 $ or $ 2 $ a total of $ 10 $ times, the first edge breaks and no more operations can be performed. At this point, $ G $ is divided into $ 2 $ connected components: $\{0\}$ and $\{1,2\}$.

Sample Explanation 2

(Updated at 10:40) By choosing vertex $ 4 $ $ 2 $ times and vertex $ 3 $ $ 3 $ times, $ G $ is divided into $ 4 $ connected components: $\{0\}$, $\{1,2\}$, $\{3\}$, and $\{4\}$.

见题面 Input 部分

见题面 Output 部分