题目描述

For Bessie the cow’s birthday, Farmer John has given her free reign over one

of his best fields to eat grass.

The field is covered in $N$ patches of grass ($1 \le N \le 1000$), conveniently

numbered $1\ldots N$, that each have a distinct quality value. If Bessie eats

grass of quality $Q$, she gains $Q$ units of energy. Each patch is connected to

up to 10 neighboring patches via bi-directional paths, and it takes Bessie $E$

units of energy to move between adjacent patches ($1 \le E \le 1,000,000$).

Bessie can choose to start grazing in any patch she wishes, and she wants to

stop grazing once she has accumulated a maximum amount of energy.

Unfortunately, Bessie is a picky bovine, and once she eats grass of a certain

quality, she’ll never eat grass at or below that quality level again! She is

still happy to walk through patches without eating their grass; in fact, she

might find it beneficial to walk through a patch of high-quality grass without

eating it, only to return later for a tasty snack.

Please help determine the maximum amount of energy Bessie can accumulate.

为了庆祝奶牛Bessie的生日，Farmer John给了她一块最好的牧场，让她自由的享用。

牧场上一共有N块草地（1≤N≤1000），编号为1...N，每块草地上牧草的质量都不同。

如果Bessie吃掉的草地上牧草质量为Q，她可以获得Q单位的能量。

每块草地最多和10块草地有相连的道路，在相连的两个草地之间走动需要消耗E单位的能量(1≤E≤1,000,000)。

Bessie可以从任意一块草地开始吃草，并且想要在获得了最多能量的时候停止。

有点遗憾的，Bessie是一头挑食的奶牛，一旦她吃过了一定质量的牧草，她就不会再吃相同或更低质量的牧草！但是她仍然很愿意路过某些草地，而不吃它们。实际上，她发现路过一块高质量的草地而不吃它，等一下返回再去享用，有时会更有利！

请帮忙计算Bessie能够获得的能量的最大值。

输入格式

The first line of input contains $N$ and $E$. Each of the remaining $N$ lines

describe a patch of grass. They contain two integers $Q$ and $D$ giving the

quality of the patch (in the range $1\ldots 1,000,000$) and its number of

neighbors. The remaining $D$ numbers on the line specify the neighbors.

1行：包含两个整数N和E。

接下来N行：每行描述一块草地，首先两个整数Q和D，分别表示草地上牧草的质量（范围1…1,000,000）和相连的草地数量。然后D个整数表示相连的草地。

输出格式

Please output the maximum amount of energy Bessie can accumulate.

输出Bessie能够获得的能量的最大值。

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

7

提示

Bessie starts at patch 4 gaining 5 units of energy from the grass there. She

then takes the path to patch 5 losing 2 units of energy during her travel.

She refuses to eat the lower quality grass at patch 5 and travels to patch 3

again losing 2 units of energy. Finally she eats the grass at patch 3 gaining 6 units of energy

for a total of 7 energy.

Note tha the sample case above is different from test case 1 when you submit.

感谢@蒟蒻orz神犇 提供翻译