문제

현석이는 생일을 맞아 유성구의 맛집들을 탐방하기로 했다. 유성구에는 $1$번부터 $N$번까지 번호가 매겨진 $N$개의 맛집이 있으며, 각 맛집은 서로 다른 맛 점수 $Q$를 가지고 있다. 현석이가 맛 점수가 $Q$인 맛집에서 식사를 하면 $Q$만큼의 만족도를 얻는다. 각 맛집은 최대 10개의 인접한 맛집과 양방향 길로 연결되어 있으며, 인접한 맛집 사이를 이동할 때마다 현석이는 $E$만큼의 체력을 소모한다. 현석이는 원하는 맛집에서 탐방을 시작할 수 있으며, 얻은 만족도의 합에서 이동하며 소모한 체력의 합을 뺀 값을 최대화하고자 한다.

단, 현석이는 입맛이 매우 까다롭다. 한 번 맛 점수가 $Q$인 음식을 먹고 나면, 이후에는 맛 점수가 $Q$보다 큰 맛집의 음식만 먹는다. 식사를 하지 않고 맛집을 지나쳐 가는 것은 가능하며, 나중에 더 맛있는 음식을 먹기 위해 이전에 식사하지 않고 지나쳤던 맛집을 다시 방문하여 식사할 수도 있다.

현석이가 얻을 수 있는 만족도의 최댓값을 구하시오.

입력

첫째 줄에 맛집의 수 $N$과 이동 시 소모되는 체력 $E$가 공백으로 구분되어 주어진다. ($1 \le N \le 1\,000$; $1 \le E \le 1\,000\,000$)

이어서 $N$개의 줄에 걸쳐 각 맛집의 정보가 주어진다. 각 줄에는 해당 맛집의 맛 점수 $Q$, 인접한 맛집의 수 $D$, 그리고 인접한 맛집들의 번호 $D$개가 공백으로 구분되어 주어진다. ($1 \le Q \le 1\,000\,000$; $0 \le D \le 10$)

모든 맛집의 맛 점수는 서로 다르다.

출력

현석이가 얻을 수 있는 만족도의 최댓값을 출력한다.

예제 입력 1

5 2
4 1 2
1 3 1 3 4
6 2 2 5
5 2 2 5
2 2 3 4

예제 출력 1

7