Ко дню рождения коровы Бесси фермер Джон дал ей право распоряжаться одним из своих лучших полей, чтобы она ела траву.

Поле покрыто n участками травы, пронумерованными от 1 до n, качество травы на каждом из которых разное. Если Бесси съест траву качества q, то получит q единиц энергии. Каждый участок соединен с 10 соседними участками двунаправленными дорогами, и для перемещения между соседними участками Бесси требуется e единиц энергии. Бесси может начать пастись на любом участке, на котором пожелает. Она прекратит пастись, как только накопит максимальное количество энергии.

К сожалению, Бесси придирчива, и поскольку она съела траву определенного качества, то уже никогда не позволит себе есть траву того же или более низкого качества. Бесси была бы рада просто пересечь участок без страха. На самом деле, ей может быть полезно просто пройтись по лугу с более качественной травой и вернуться туда позже, чтобы поесть.

Пожалуйста, помогите Бесси определить максимальное количество единиц энергии, которое она сможет накопить.

Входные данные

В первой строке даны значения n (1 ≤ n ≤ 1000) и e (1 ≤ e ≤ 106). Каждая из остальных n строк описывает следующий участок с травой. Каждому из них сначала присваиваются два целых числа q и d - качество (число в диапазоне 1..106) и количество соседних участков. Остальные числа d в ряду описывают соседние участки своими номерами.

Выходные данные

Выведите максимально возможную энергию, которую может получить Бесси.

Пример

Бесси начинает пастись на лугу 4 и собирает 5 единиц энергии. Затем он уходит на поляну 5, теряя на своем движении 2 единицы энергии. Она отказывается есть траву более низкого качества на лугу 5 и идет на луг 3, теряя еще 2 единицы энергии. Наконец, Бесси ест траву на лугу 3, тем самым добавляя еще 6 единиц энергии. Таким образом, он собирает в общей сложности 7 единиц энергии.