問題

各頂点が数値を持つ有向ツリーが与えられる． あなたは，コスト 1 にて，ある頂点の数値を 1 変更することができる． 即ち，ある頂点の数値を 1 増やすか1 減らすためにコストが 1 かかる． 変更後の数値に大きさなどの制限はない．

あなたは，与えられたツリーを「じょうしょうツリー」にしたい．じょうしょうツリーとは，各頂点の持つ数値が，その全ての子の数値よりも大きいツリーのことである．ツリーが入力されたとき，そのツリーをじょうしょうツリーにするために必要な最小のコストを求めるプログラムを作成せよ．

図 1: 入力されるツリーの例
図 2: 図 1 の木の数値を変更してじょうしょうツリーにした例

---

入力

N C_1
P_2 C_2
...
P_N C_N

入力の 1 行目には，ツリーの頂点数 N と根の頂点が持つ数値 C_1 が与えられる. ツリーは N 個の頂点を持ち，頂点には 1 から N までの番号が付いている．ツリーは頂点 1 である．

入力の 2 行目から N 行目には，各頂点に関する情報が与えられる． i 行目には，頂点 i の親の頂点の番号 P_i と，頂点 i に書かれた数字 C_i が与えられる．

出力

最小の合計コストを 1 行に出力せよ.

制約

• 1 \leq N \leq 10^5
• 1 \leq P_i < i
• -10^9 \leq C_i \leq 10^9

部分点

この問題の判定には，50点分のテストケースのグループが設定されている． このグループに含まれるテストケースの入力は追加で以下の条件を満たす．

• N \leq 50
• -50 \leq C_i \leq 50

---

入力例 1

8 6
1 1
2 1
2 3
1 9
5 6
6 6
6 2

入力例 1 に対する出力例

8

この入力は上図に対応している．入力は図 1 に相当し，例えば図 2 のように数値を変更すればコスト 8 にてツリーをじょうしょうツリーにできる．

---

入力例 2

4 5
1 5
2 5
3 5

入力例 2 に対する出力例

4

親の数値は子の数値よりも真に大きくなければならず，等しくてはいけないことに注意せよ．