День народження Бессі#11172
На честь дня народження Бессі Фермер Джон дозволив їй вільно пастися на одному з найкращих своїх полів.
Поле складається з ділянок з травою, пронумерованих числами , кожна з яких має унікальне значення якості трави. Якщо Бессі з'їдає траву якості , вона отримує одиниць енергії. Кожна ділянка з'єднана не більше ніж з сусідніми ділянками двонаправленими дорогами, а для переходу між сусідніми ділянками Бессі витрачає одиниць енергії.
Бессі може обрати будь-яку ділянку як початкову позицію. Вона хоче пастися доти, доки не накопичить максимально можливу кількість енергії.
На жаль, Бессі — перебірлива корова: після того як вона з'їсть траву певної якості, вона більше ніколи не буде їсти траву такої самої або нижчої якості. Однак Бессі зовсім не проти проходити через ділянки, не з'їдаючи траву, що там росте. Більше того, їй може бути вигідно пройти через ділянку з травою високої якості, не з'їдаючи її, щоб пізніше повернутися за смачною закускою.
Допоможіть визначити максимальну кількість енергії, яку Бессі може накопичити.
У першому рядку знаходяться два цілих числа та e~(1 \le n \le 1000, 1 \le e \le 10^6).
Кожен з наступних рядків описує одну ділянку з травою. Кожен рядок містить два цілих числа та , де q~(1 \le q \le 10^6) — якість трави на цій ділянці, а — кількість сусідніх ділянок.
Наступні цілих чисел у цьому рядку задають номери сусідніх ділянок.
Виведіть максимальну кількість енергії, яку Бессі може накопичити.
Бессі починає з ділянки і отримує одиниць енергії, з'ївши траву, що там росте. Потім вона йде дорогою до ділянки , втрачаючи по дорозі одиниці енергії. Вона відмовляється їсти траву нижчої якості на ділянці і повертається до ділянки , втрачаючи ще одиниці енергії. Нарешті, вона з'їдає траву на ділянці , отримуючи одиниць енергії. У підсумку вона отримує одиниць енергії.
Приклад 1