Description

现在某组织中（记作R）有n个人，他们的联络网形成一棵以Saltless为根的树，有边相连代表两人可以直接联络。
每个人有一个代号，Saltless代号为1，且除Saltless外每个人的父节点的代号小于他自己的代号。
由于某些原因，Saltless给R的成员分别下达紧急任务，R需要分成m组行动，每个组必须满足如下条件：
	1、每个组员仅分在本组中
	2、至少有一个组员
	3、任意两个组员无需通过本组外的人就可以联络（但可以通过本组组员进行联络）

每个人有一个能力指数，一个组的能力指数是全组人能力指数之和。
对于任意一种正确的分组，平均度就是m组中最小能力指数。为了分组较为平均，Saltless希望平均度尽可能大。

Input

第一行为三个数：n,m,和Saltless的能力指数（1<=m<=n<=10000）。
接下来n-1行，每行两个数：此人的父节点代号和他的能力指数（能力指数值为正整数，不超过30，行数就是他本身的代号） 

Output

输出格式： 一个数，表示最大的平均度。

Sample Input

7 2 2
1 4
1 5
2 1
2 2
3 4
4 3

Sample Output

10

HINT

Source