問題文

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 点が得られる。

入力例 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