班长的任务

班长的任务

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

背景

十八居士的毕业典礼(1)

描述

福州时代中学2009届十班同学毕业了,于是班长PRT开始筹办毕业晚会,但是由于条件有限,可能每个同学不能都去,但每个人都有一个权值,PRT希望来的同学们的权值总和最大。

十班有一个周密的电话通知网络,它其实就是一棵树,根结点为班长PRT,由她来负责通知她的下线(也就是儿子节点),下线们继续通知自己的下线(不一定每个下线都要通知),任何人都可以不去:”
为了使权值总和最大,班长想安排一下人,但是人数很多,人脑是难以应付的,所以她找到十八居士,让他编程用电脑解决。

格式

输入格式

输入第一行两个整数n,m表示有n位同学,至多只能去m位同学。(1<=m<=n)
接下来2*n行,每两行代表一个同学的信息(如果这位同学没有子节点,就只有一行)。

每个同学的第一行两个整数p,s,表示这位同学权值为p,子节点个数s;(-100<=p<=100)
第二行s个整数,表示这位同学的子节点的编号。

班长的编号一定为1。

对于20%数据1<=n<=10
对于60%数据1<=n<=100
对于100%数据1<=n<=1000

输出格式

输出一个整数,表示权值的最大值。

样例1

样例输入1

8 5
100 2
2 3
79 2
4 5
109 3
6 7 8
100 0
100 0
100 0
101 0
108 0

样例输出1

518

提示

来源

181818181818

十八居士的毕业典礼

未参加
状态
已结束
规则
OI
题目
4
开始于
2009-08-29 19:00
结束于
2009-08-29 22:00
持续时间
3.0 小时
主持人
参赛人数
657