题目描述

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

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

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

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

输入格式

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

输出格式

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

样例

输入样例

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

输出样例

7

提示

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

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