选课

TimeLimit:1000MS  MemoryLimit:128MB
64-bit integer IO format:%lld
未提交 | 登录后收藏
Problem Description

大学里实行学分。每门课程都有一定的学分,学生只要选修了这门课,并

通过考核就能获得相应的学分。

学生最后的学分是他各门课学分的总和。

每个学生都要选择规定数量的课程。其中有些课程可以直接选修,

有些课程需要一定的基础知识,必须在选了其他的一些课程的基础上才能选修。

例如,《剥皮术》就必须在选修了《屠龙术》后才能选修。

我们称《屠龙术》是《剥皮术》的先修课。

每门课的直接先修课最多之有一门。两门课也可能存在相同的先修课。

每门课都有一个课号,课号依次是1,2,3……。以下表为例说明。

      

课号

先修课号

学分

1

1

2

1

1

3

2

3

4

3

5

2

4

 

上表中12的先修课,即如果要选修2,则1必须已被选过。

同样,要选修3,那么12都一定被选修过。

每个学生可选的课程总数是一定的,请找出一种方案,使得到的总学分最多。



Input

第一行包括两个正整数MN(中间一个空格),其中M表示总课程数,

1<=M<=100),N表示每个学生最多可选的课程总数。(1<=N<=M)。

以下M行每行代表一门课,课号依次是1,2,...,M。每行两个数,

第一个数为这门课的直接先修课的课号(若不存在则为0),第二个数为该门课的学分。

学分是不超过20的正整数。

测试数据保证学生能够选满N门课。


Output

输出一行,表示实际所选课程学分之和。

SampleInput
7 4
2 2
0 1
0 4
2 1
7 1
7 6 
2 2
SampleOutput
13
Submit
题目统计信息详细
总AC数4
通过人数4
尝试人数4
总提交量4
AC率100.00%
AC该题后可以添加标签
贴完标签可以获得20ACB。
并且可以获得本题所有提交代码查看权限。
点击标题可以显示标签。
如果你还没认真思考过这题,请不要查看标签
如果您已经通过了该题,请务为该题贴上标签
出处

T^T Online Judge

[BUG反馈] [FAQ] [闽ICP备17026590号-1]
当前版本:3.24 系统时间: