问题描述

有一个由 $N$ 个顶点和 $N-1$ 条边组成的树状糖果 $G$。

每个顶点编号从 $0$ 到 $N-1$，每条边编号从 $1$ 到 $N-1$。

根节点是顶点 $0$。边 $i$ 是连接顶点 $i$ 和 $p_i$ 的无向边，硬度为 $H_i$。

您要重复以下操作，试图将糖果 $G$ 分成更多的连通分量：

• 选择根节点 $0$ 以外的一个顶点 $X$，用双手拉动根节点 $0$ 和顶点 $X$。
• 连接根节点 $0$ 和顶点 $X$ 之间的路径上的所有边的硬度减少 $1$。
• 硬度变为 $0$ 的边被切断消失。
• 根据该操作，成为不与根节点连通的顶点不能再被选中。

请计算经过操作后，$G$ 的最大连通分量数目。

约束条件

• $2 \le N \le 5000$
• $0 \le p_i < i$
• $1 \le H_i \le 10^9$
• 输入均为整数。

子任务

本问题设有子任务。

• 如果满足 $N \le 300$ 的输入得到正确答案，则得到 $500$ 分。

输入

从标准输入中以以下格式给出输入。

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

输出

输出经过操作后，$G$ 的最大连通分量数目。

输入示例 1

3
0 10
1 20

输出示例 1

2

选择顶点 $1$ 或 $2$ 各 $10$ 次，则第 $1$ 条边被切断，无法进行更多操作。

此时，$G$ 被分成了两个连通分量 $\\{0\\},\\{1,2\\}$。

输入示例 2

5
0 5
1 10
1 3
2 2

输出示例 2

4

选择顶点 $4$ $2$ 次，选择顶点 $3$ $3$ 次，则得到了 $4$ 个连通分量 $\\{0\\},\\{1,2\\},\\{3\\},\\{4\\}$。

输入示例 3

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

输出示例 3

6