Фермер Джон подарил корове Беси на день рождения одно из лучших полей.
Поле покрыто \(N\) областями травы (\(1 \le N \le 1000\)), последовательно пронумерованных
\(1\ldots N\), имеющих различные показатели качества.
Если Беси ест трау с качеством \(Q\), она получает \(Q\) единиц энергии. Каждая область соединена максимум с 10 соседними областями двунаправленными дорожками, и Беси требуется \(E\) единиц энергии чтобы перейти на соседнюю область
(\(1 \le E \le 1,000,000\)).
Беси может выбрать в качестве начала поедания любую область, которую пожелает, Она заканчивает поедание, когда соберёт максимальное количество энергии.
К несчастью, Беси - разборчивая корова, и если она съела траву определённого качества, то она никогда больше не ест траву такого же или более низкого качества. Но она может проходить через области, не кушая травы. Более того, она может найти выгодным пройти через область с травой высокого качества, не поедая её, чтобы затем вернуться сюда позже и поесть.
Пожалуйста, определите максимальное количество энергии, которое может собрать Беси.
ФОРМАТ ВВОДА (файл buffet.in):
Первая строка ввода содержит \(N\) и \(E\). Каждая из последующих \(N\)
Строк описывает область травы двумя целыми числами \(Q\) и \(D\) определяющими качество травы (в диапазоне \(1\ldots 1,000,000\)) и количество ей соседей, оставшиеся \(D\) чисел указывают её соседей.
ФОРМАТ ВЫВОДА (файл buffet.out):
Выведите максимальное количество энергии, которое может собрать Беси.
ПР�МЕРВВОДА:
5 2
4 1 2
1 3 1 3 4
6 2 2 5
5 2 2 5
2 2 3 4
ПР�МЕРВЫВОДА:
7
Беси начинает в области 4, собирает 5 единиц энергии, затем она перемещается в область 5, теряя 2 единицы энергии во время перехода. Затем она отказывается есть траву более низкого качества в области 5 и переходит в область 3 опять теряя 2 единицы энергии. Там она получает +6 единиц энергии, поедая траву. Всего у неё становится 7 единиц энергии.