题目描述

小 A 爱上了小 B！！！可是小 A 相对小 B 太弱，所以她当然不会同意小 A 的请求。小 A 苦苦追求，最终小 B 就提这样的条件：

• 小 B 有 $n$ 个下属（不包括小 B）组成了树状结构，小 B 在顶端，其他人都有一个直属上司。
• 小 B 编号 $0$，其他人编号 $1 \sim n$。
• 对于第 $i$ 人，如果这个人没有下属，那么小 A 可以给他 $A_i$ 元钱，则他会向他的直属上司写一封信，表示小 A 向小 B 求爱；
• 如果他的直属下属有占比不小于 $\dfrac{A_i}{T}$ 的人写信表示小 A 向小 B 求爱，那么他也会向他的直属上司写一封信，表示小 A 向小 B 求爱。
• 如果小 B 的直属下属有占比不小于 $\dfrac{C}{T}$ 的人写信表示小 A 向小 B 求爱，那么她会同意小 A 的请求。

请问小 A 至少需要给多少钱才会让小 B 同意小 A 的求爱。

输入格式

第一行三个整数 $n, T, C$。

然后 $n$ 行，第 $i$ 行两个整数 $B_i, A_i$，$B_i$ 表示 $i$ 的直属上司，保证 $B_i < i$。

输出格式

需要给的钱数。

14 5 3
0 3
0 3
1 10
1 10
2 3
2 10
2 3
5 10
7 10
5 10
7 10
5 10
7 10
5 10

50

提示

对于 $20 \%$ 的数据，没有直属下属的人数 $\le 15$。
对于 $40 \%$ 的数据，$n \le 2000$。
另有 $10 \%$ 的数据，$B_i = 0$。 另有 $10 \%$ 的数据，$C = 1$ 且对于有直系下属的人 $T / A_i > n$。
另有 $10 \%$ 的数据，$B_i = i - 1$。

对于 $100 \%$ 的数据，$1 \le n \le 500000$，$1 \le T \le {10}^9$，$B_i < i$，$1 \le A_i \le T$。