恋爱

题目描述

小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

输出格式


需要给的钱数。

输入输出样例

输入样例 #1

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

输出样例 #1

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