题目描述

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

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

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

输入格式

第一行三个整数n、T、C。

然后n行，第i行两个整数Bi、Ai，Bi表示i的直属上司，保证Bi<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%的数据没有直属下属的人数<=15

对于40%的数据n<=2000

另有10%的数据Bi=0

另有10%的数据C=1且对于有直系下属的人T/Ai>n

另有10%的数据Bi=i-1

对于100%数据n<=500000 T<=10亿 Bi<i 0<Ai<=T