#863. 选课问题

选课问题

说明

在大学里每个学生,为了达到一定的学分,必须从很多课程里选择一些课程来学习,在课程里有些课程必须在某些课程之前学习,如高等数学总是在其它课程之前学习。现在有 NN 门功课,每门课有个学分 aia_i ,每门课有一门或没有直接先修课(若课程 aa 是课程 bb 的先修课即只有学完了课程 aa,才能学习课程 bb)。一个学生要从这些课程里正好选择 MM 门课程学习,问他能获得的最大学分是多少?


输入格式


输入第一行包含两个整数 $N,M$
接下来 $N$ 行,每行包含两个整数 $f_i,a_i$,$f_i$ 表示第 $i$ 个门课的先修课($0$表示没有先修课),$a_i$ 表示第 $i$ 门课的学分

其中: $( 1 \leq N,M,a_i \leq 300)$

输出格式

输出一个最多的学分

样例1

7 4 
2 2 
0 1 
0 4 
2 1 
7 1
7 6
2 2
13

样例2

4 3
2 3
3 3
1 3
0 10
0