问题 2729 --czy的后宫5

2729: czy的后宫5

题目描述

  czy要召集他的妹子,但是由于条件有限,可能每个妹子不能都去,但每个妹子都有一个美丽值,czy希望来的妹子们的美丽值总和最大(虽然……)。
czy有一个周密的电话通知网络,它其实就是一棵树,根结点为czy,他可以通知一些妹子(毕竟他不认识他的所有妹子嘛),称为他的下线(也就是儿子节点),下线们继续通知自己的下线。任何妹子都可以不去,但是任何一个妹子如果要去,则她的上线(也就是她的父亲节点)一定要去。
为了使妹子美丽值总和最大,czy想安排一下,(非强制)让一些妹子去。但是妹子数很多,人脑是难以应付的,所以他想让你用电脑解决。

输入

输入第一行两个整数n,m表示有n个妹子,至多只能去m个妹子。(1<=m<=n)
接下来2*n行,每两行代表一个妹子的信息(如果这个妹子没有子节点,就只有一行)。
每个妹子的第一行两个整数p,s,表示这个妹子美丽值为p,子节点个数s;(-100<=p<=100)
第二行s个整数,表示这个妹子的子节点的编号。czy的编号一定为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

提示

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

序号 标题 作者 发表时间 费用 订购数 操作