베시의 생일 뷔페

베시의 생일을 맞아 농부 존은 자기 목장에서 가장 좋은 밭 하나를 골라 베시가 마음껏 풀을 뜯게 해 주었다.

밭에는 풀밭이 $N$개 있고 ($1 \le N \le 1000$), $1$번부터 $N$번까지 번호가 붙어 있다. 풀밭의 품질 값은 모두 서로 다르다. 베시가 품질이 $Q$인 풀을 먹으면 에너지 $Q$를 얻는다. 각 풀밭은 최대 $10$개의 이웃 풀밭과 양방향 길로 이어져 있고, 인접한 두 풀밭 사이를 한 번 이동할 때마다 에너지 $E$를 쓴다 ($1 \le E \le 1\,000\,000$). 베시는 원하는 풀밭 아무 곳에서나 풀을 뜯기 시작할 수 있고, 모은 에너지가 가장 많아지는 순간에 멈추려 한다.

문제는 베시의 입맛이 까다롭다는 것이다. 어떤 품질의 풀을 한 번 먹고 나면 그 뒤로는 그 품질과 같거나 더 낮은 품질의 풀을 절대 먹지 않는다. 풀을 먹지 않고 풀밭을 그냥 지나가는 것은 상관없다. 품질이 높은 풀밭을 일부러 먹지 않고 지나쳤다가 나중에 돌아와 먹는 편이 이득일 수도 있다.

베시가 모을 수 있는 에너지의 최댓값을 구하는 프로그램을 작성하라.

첫째 줄에 $N$과 $E$가 공백으로 구분되어 주어진다.

이어지는 $N$개의 줄은 $1$번 풀밭부터 $N$번 풀밭까지 차례로 설명한다. 각 줄에는 그 풀밭의 품질 $Q$ ($1 \le Q \le 1\,000\,000$)와 이웃의 개수 $D$ ($0 \le D \le 10$)가 먼저 주어지고, 그 뒤에 이웃 풀밭의 번호가 $D$개 주어진다. 길은 양방향이므로 각 길은 양쪽 풀밭의 줄에 모두 나타난다.

베시가 모을 수 있는 에너지의 최댓값을 한 줄에 출력한다.

첫 번째 예제에서 베시는 4번 풀밭에서 시작해 그곳의 풀을 먹고 에너지 $5$를 얻는다. 이어서 5번 풀밭으로 이동하며 에너지 $2$를 쓴다. 5번 풀밭의 풀은 품질이 더 낮아 먹지 않고, 다시 에너지 $2$를 쓰며 3번 풀밭으로 간다. 마지막으로 3번 풀밭의 풀을 먹어 에너지 $6$을 얻고, 합계는 $7$이 된다.