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, conveniently numbered 1..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. 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.

Input

The first line contains n (1 ≤ n ≤ 1000) and e (1 ≤ e ≤ 106). 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..106) and its number of neighbors. The remaining d numbers on the line specify the neighbors.

Output

Print the maximum amount of energy Bessie can accumulate.

Example

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.