当前没有测试数据。

【例题4】选课方案

题目描述

在大学里，每个学生为了达到一定的学分，必须从很多课程里选择一些课程来学习，有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有$n$门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程$a$是课程$b$的先修课即只有学完了课程$a$，才能学习课程$b$）。一个学生要从这些课程里选择$m$门课程学习，问他能获得的最大学分是多少？

输入格式

第一行有两个整数$n$，$m$。接下来的$n$行，第$i+1$行包含两个整数$k_{i}$，$s_{i}$，$k_{i}$表示第$i$门课的直接先修课，$s_{i}$表示第$i$门课的学分。若$k_{i}=0$表示没有直接先修课。

输出格式

一个整数，选$m$门课程的最大得分。

数据范围与提示

对于$100\%$的数据，$1 \leq k_i \leq n$，$m \leq 300$，$1 \leq s_i \leq 20$。

样例

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

13