Bessie's Birthday Buffet

For Bessie the cow's birthday, Farmer John picked the best field on his farm and let her graze there as she likes.

The field holds $N$ patches of grass ($1 \le N \le 1000$), numbered $1$ through $N$. The quality values of the patches are all different. When Bessie eats grass of quality $Q$, she gains $Q$ units of energy. Each patch is joined to at most $10$ neighboring patches by bidirectional paths, and every move between two adjacent patches costs Bessie $E$ units of energy ($1 \le E \le 1\,000\,000$). Bessie may start grazing at any patch she likes, and she stops at the moment her accumulated energy is largest.

Bessie is a picky cow. Once she eats grass of some quality, she never again eats grass of that quality or lower. Walking through a patch without eating it is fine. Passing a high quality patch on purpose and coming back for it later can pay off.

Compute the maximum amount of energy Bessie can accumulate.

The first line contains $N$ and $E$, separated by a space.

Each of the next $N$ lines describes one patch, in order from patch $1$ to patch $N$. A line starts with the quality $Q$ of the patch ($1 \le Q \le 1\,000\,000$) and the number of neighbors $D$ ($0 \le D \le 10$), followed by the $D$ neighbor numbers. Paths are bidirectional, so every path appears on the lines of both of its patches.

Print the maximum amount of energy Bessie can accumulate on one line.

In the first example Bessie starts at patch 4 and eats the grass there for $5$ units of energy. She then moves to patch 5, spending $2$ units of energy. The grass at patch 5 has lower quality, so she leaves it and spends another $2$ units of energy moving to patch 3. Finally she eats the grass at patch 3 for $6$ units of energy, so her total is $7$.