#P5420. Bessie's Birthday Buffet

Bessie's Birthday Buffet

题目描述

为了庆祝奶牛贝西的生日,农夫约翰让她在他最好的田地里自由地吃草。

田地覆盖着N{N}片草地1{(1≤}N{N≤}1000{1000)},方便地编号为1{1…}N{N,}每个都有一个不同的质量值。如果贝西吃了质量为Q{Q}的草,她获得了Q{Q}能量单位。每个面片通过双向路径连接到多达10{10}个相邻面片,在相邻面片之间移动需要贝西E{E}能量单位1{(1≤}E{E≤}1,000,000).{1,000,000). }贝西可以选择在她希望的任何地方开始放牧,她希望在积累了最大能量后停止放牧。

不幸的是,贝西是一头挑剔的牛,一旦她吃了某种质量的草,她就再也不会吃那种质量或低于那种质量的草了!她仍然很乐意穿过一块块地而不吃草;事实上,她可能会发现,在一片高质量的草地上行走而不吃,然 后回来吃美味的小吃是有益的。

请帮助确定贝西可以积累的最大能量。

输入格式

第一行输入包含N{N}E{E}。其余N{N}行中的每一行描述一片草地。它们包含两个整数Q{Q}D{D,}表示面片的质量(范围为1{1…}1000000{1000000)}及其邻域数。行上剩余的D{D}数指定了相邻的数。

输出格式

请输出贝西可以积累的最大能量。

样例

输入样例

5 2
4 1 2
1 3 1 3 4
6 2 2 5
5 2 2 5
2 2 3 4

输出样例

7

提示

贝西从第4{4}补丢始,从那里的草地获得5{5}个单位的能量。然后,她选择了补丁5{5,}在旅行中损失了2{2}个单位的能量。她拒绝在补丁5{5}吃质量较低的草,并再次前往补丁3{3 ,}损失2{2}个单位的能量。最后,她在补丁3{3}吃了草,获得了6{6}个能量单位,总共7{7}个能量。

请注意,当您提交时,上面的示例案例与测试案例1{1}不同。