問題文

$N$ 頂点 $N-1$ 辺からなる根付き木の形をしたグミ $G$ があります。

頂点には $0$ から $N-1$ の番号が、辺には $1$ から $N-1$ の番号がついています。

根は頂点 $0$ です。辺 $i$ は頂点 $i$ と $p_i$ を結ぶ無向辺であり、硬さは $H_i$ です。

あなたは以下の操作を繰り返して、このグミ $G$ をより多くの連結成分に分けようとしています。

• 根 $0$ 以外の $1$ つの頂点 $X$ を選び、根 $0$ と $X$ を両手で引っ張る。
• 根 $0$ と $X$ を結ぶパス上にあるすべての辺の硬さが $1$ 減少する。
• 硬さが $0$ になったすべての辺はちぎれて消滅する。
• これによって根と連結でなくなった頂点は $2$ 度と選ぶことができない。

操作を繰り返したあとの、$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$ $:$ $p_{N-1}$ $H_{N-1}$

出力

操作を繰り返したあとの、$G$ の連結成分の個数の最大値を出力せよ。

入力例 1

3
0 10
1 20

出力例 1

2

頂点 $1$ または $2$ を合計 $10$ 回選ぶと、$1$ 番目の辺がちぎれ、これ以上操作ができなくなります。

このとき、$G$ は $\\{0\\},\\{1,2\\}$ という $2$ 個の連結成分に分かれています。

入力例 2

5
0 5
1 10
1 3
2 2

出力例 2

4

(10:40 更新) 頂点 $4$ を $2$ 回選び、頂点 $3$ を $3$ 回選ぶと、$\\{0\\},\\{1,2\\},\\{3\\},\\{4\\}$ という $4$ 個の連結成分に分かれます。

入力例 3

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

出力例 3

6