Distribution:分发小册子

日本信息奥林匹克委员会是一个上下关系非常严格的组织。委员长有一个，除委员长以外的人都只有一个上级。而且，属于委员会的人，每个人都有干劲的数值。现在，在信息奥林匹克日本委员会中，决定启动一个新的项目。该项目能否顺利进行，与参加的人数无关，而在于参加的人的干劲的总和。

委员长制作了m册关于那个项目的详细说明。参加项目的人，一定要读册子，读了册子的人一定要参加项目。起初，委员长拥有所有m册。委员长及得到一本以上册子的人，先看册子，有部下就把册子交给部下。下属，就是以这个人为他或她的上司的人。一本册子可以交给部下中的一个人。同一个部下可以给两本以上的册子，有的部下可以一本册子也不给。读过一册，就不必在手边留册了。

现在输入每个人的上司和干劲的数值，以及制作的册子的册数m，要求编写出回答参加项目的人的干劲总和的最大值的程序。

Input.

输入的第一行以空白为分隔写有两个整数n,m(1<=n<=10000,1<=m<=1000)。这表示信息奥林匹克日本委员会的人数是n人，制作的册子的册数是m册。

接下来的n行写着每个人的上司和干劲的数值。在第i+1行(1<=i<=n)中以空白为分隔写有两个整数si,ai(0<=si<i,1<=ai<=10000)。这表示人i的上司是人si，人i的干劲数值是ai。si为0时，人i表示委员长。(根据si<i，某人的上司必定有比他的号码更小的号码，人1必定是委员长。)

Output.

用一行输出一个表示参与项目的人的干劲总和的最大值的整数。

评测标准 数据的50%满足n<=500,m<=100。

例

输入

5 2

0 10

1 3

2 5

2 2

1 4

标准输出

22