Bessie's Birthday Buffet#11172
For Bessie's birthday, Farmer John has given her free rein over one of his best fields to graze.
The field is covered with patches of grass, conveniently numbered , each with a distinct quality value. If Bessie eats grass of quality , she gains units of energy. Each patch is connected to at most neighboring patches by bidirectional paths, and it takes Bessie units of energy to travel between adjacent patches.
Bessie may choose any patch as her starting point. She wants to graze until she has accumulated as much energy as possible.
Unfortunately, Bessie is a picky bovine: once she eats grass of a certain quality, she will never eat grass of that quality or lower again. However, she is perfectly happy to walk through patches without eating their grass. In fact, she may find it beneficial to walk through a patch with 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.
The first line contains two integers and e~(1 \le n \le 1000, 1 \le e \le 10^6).
Each of the next lines describes a patch of grass. Each line contains two integers and , where is the quality of the grass in the patch (1 \leq q \leq 10^6) and is the number of neighboring patches.
The remaining integers on the line specify the neighboring patches.
Print the maximum amount of energy Bessie can accumulate.
Bessie starts at patch and gains units of energy from the grass there. She then takes the path to patch , losing units of energy along the way. She refuses to eat the lower-quality grass at patch and travels back to patch , losing another units of energy. Finally, she eats the grass at patch , gaining units of energy, for a total of units of energy.
Beispiel 1