Preparing NOJ

A选课

1000ms 65536K

Description:

学校实行学分制。每门的必修课都有固定的学分,同时还必须获得相应的选修课程学分。学校开设了N门的选修课程,学生有M天的时间学习。学生花一定量的天数选修一门课并考核通过就能获得相应的学分。

  在选修课程中,有一门课程可以直接选修,其它课程则需要一定的基础知识,必须在选了其它的一些课程的基础上才能选修。例如《Frontpage》必须在选修了《Windows操作基础》之后才能选修。我们称《Windows操作基础》是《Frontpage》的先修课。每门课的直接先修课最多只有一门。两门课也可能存在相同的先修课。每门课都有一个课号,依次为1,2,3,…。

  你的任务是为自己确定一个选课方案,使得你能得到的学分最多,并且必须满足先修课优先的原则。假定课程之间不存在时间上的冲突。

  希望你能合理分配时间,获得尽量多的学分。


Input:

输入共N + 1行。

第一行共两个数N、M,由空格隔开。含义如前述。

第2至N + 1行,每行共三个数p, t, v由空格隔开。第i + 1行为第i门选修课的信息。p表示i的先修课,t表示修i所需天数,v表示i的学分。若p = 0则表示i可以直接选修,没有先修课。


Output:

输出共一行。

第一行共一个数,即最多修多少学分。保证答案不超过100000。


Sample Input:

5 24
5 9 5
3 10 10
0 7 10
2 7 2
3 7 1

Sample Output:

22

Note:

 

本题由旧版NOJ导入,来源:NUAA_孙黎

Info

NOJ

Provider NOJ

Code NOJ1168

Tags

Submitted 9

Passed 0

AC Rate 0%

Date 04/20/2019 10:03:10

Related

Nothing Yet