나라의 심장부

그래피아라는 나라가 전쟁에 휘말렸다. 이웃 나라들은 그래피아가 번영하는 도시들을 세우고 그 도시들을 고속도로망으로 연결하는 모습을 오랫동안 시샘하며 지켜보았고, 이제 그 몫을 차지하려 한다.

그래피아는 고속도로로 연결된 여러 도시로 이루어져 있다. 지형이 험해 도시 사이를 오갈 수 있는 방법은 고속도로뿐이다. 각 도시에는 일정 수의 병력이 주둔한다. 군 지휘부가 한 도시를 방어하려면 최소 $K$명의 병력이 필요하다. 어떤 도시는 그 도시에 주둔한 병력과, 중간에 다른 도시를 거치지 않고 고속도로 하나로 직접 연결된 모든 도시의 병력으로 방어한다. 그보다 멀리 있는 병력은 제때 도착하지 못한다. 적은 한 번에 한 도시만 공격하므로, 한 도시의 병력은 그 도시 자신은 물론 인접한 도시의 방어에도 쓰일 수 있다. 만약 어떤 도시를 방어할 수 없다면, 지휘부는 그 도시의 병력이 함락되어 더 이상 그래피아 방어에 도움이 되지 못한다고 보아야 한다.

아래 예시 그림에서 $K = 10$일 때, 도시 C는 잘 방어되는 것처럼 보이지만 결국 함락된다.

그래피아의 지도부는 나라의 심장부, 곧 다른 모든 도시가 함락되더라도 서로를 방어해 낼 수 있는 가장 큰 도시 집합을 찾고자 한다.

좀 더 형식적으로, 한 도시가 자기 자신과 인접한 도시들의 병력을 모두 합해 $K$명 이상을 모을 수 있으면 그 도시는 방어 가능하다. 어떤 도시 집합이 방어 가능하다는 것은, 그 집합에 속한 모든 도시가 오직 자기 자신과 그 집합 안에 있는 인접 도시의 병력만으로 방어 가능하다는 뜻이다. 나라의 심장부는 가장 큰 방어 가능한 도시 집합이다. 즉, 그보다 더 많은 도시를 포함하는 방어 가능한 집합은 존재하지 않는다.

입력은 여러 개의 데이터 집합으로 이루어진다. 각 데이터 집합은 두 정수 $N$과 $K$로 시작한다. $N$ ($3 \le N \le 1000$)은 도시의 수이고, $K$는 한 도시를 방어하는 데 필요한 병력 수이다. 도시는 $0$번부터 $N-1$번까지 번호가 매겨져 있다.

다음 $N$개의 줄은 $0$번 도시부터 차례로 각 도시를 설명한다. 각 줄은 그 도시에 주둔한 병력 수를 나타내는 정수 $T$ ($0 \le T \le 10000$)로 시작하고, 이어서 그 도시에서 나가는 고속도로의 수 $M$, 그리고 그 고속도로들이 향하는 도시 번호 $M$개가 온다. 한 도시의 목록 안에서 도시 번호는 모두 서로 다르며, 어떤 고속도로도 한 도시를 자기 자신과 연결하지 않는다. 고속도로는 양방향이다. 즉, 도시 $i$가 도시 $j$의 목록에 있으면 도시 $j$도 반드시 도시 $i$의 목록에 나타난다.

입력은 공백으로 구분된 두 개의 $0$으로 이루어진 줄로 끝난다.

각 데이터 집합마다 두 정수를 한 줄에 출력한다. 첫 번째는 나라의 심장부에 속한 도시의 수이고, 두 번째는 나라의 심장부에 속한 도시들의 병력 총합이다. 두 정수 사이에는 공백 하나를 둔다. 출력들 사이에 빈 줄을 넣지 않는다.