День народження Бессі
До дня народження корови Бессі фермер Джон надав їй можливість вибрати одне зі своїх найкращих полів для випасу.
Поле складається з n ділянок трави, пронумерованих від 1 до n, причому якість трави на кожній ділянці різна. Якщо Бессі з'їсть траву якості q, вона отримає q одиниць енергії. Кожна ділянка з'єднана з 10 сусідніми ділянками двонаправленими дорогами, і для переміщення між сусідніми ділянками Бессі потрібно e одиниць енергії. Бессі може почати пастися на будь-якій ділянці за своїм вибором. Вона припинить пастися, як тільки накопичить максимальну кількість енергії.
Однак Бессі вибаглива: якщо вона з'їла траву певної якості, вона більше не їстиме траву тієї ж або нижчої якості. Вона може просто пройти через ділянку з травою вищої якості, щоб повернутися пізніше і поїсти.
Допоможіть Бессі визначити максимальну кількість одиниць енергії, яку вона може накопичити.
Вхідні дані
У першому рядку подано значення n (1 ≤ n ≤ 1000) і e (1 ≤ e ≤ 10^6). Кожен з наступних n рядків описує ділянку з травою. Кожен рядок починається з двох цілих чисел q і d - якість трави (число в діапазоні 1..10^6) і кількість сусідніх ділянок. Решта d чисел у рядку вказують на номери сусідніх ділянок.
Вихідні дані
Виведіть максимально можливу енергію, яку може отримати Бессі.
Приклад
Бессі починає пастися на ділянці 4 і отримує 5 одиниць енергії. Потім вона переходить на ділянку 5, втрачаючи 2 одиниці енергії. Вона відмовляється їсти траву нижчої якості на ділянці 5 і переходить на ділянку 3, втрачаючи ще 2 одиниці енергії. Нарешті, Бессі їсть траву на ділянці 3, отримуючи ще 6 одиниць енергії. Таким чином, вона накопичує загалом 7 одиниць енергії.