제이미의 연락처 그룹 나누기

제이미(Jamie)는 인기가 많아 친구가 매우 많고, 그래서 휴대폰에 아주 긴 연락처 목록을 가지고 있습니다. 목록이 너무 길어져서 친구의 번호를 찾으려면 전체 목록을 훑어보는 데 오랜 시간이 걸립니다. 제이미의 가장 친한 친구이자 프로그래밍 천재인 당신은, 연락처를 여러 그룹으로 나누되 가장 큰 그룹의 크기를 최소화하라고 제안합니다. 그러면 그룹 안에서 친구의 번호를 훨씬 쉽게 찾을 수 있습니다.

제이미는 당신의 조언을 받아들여 친구들의 이름 전체 목록과, 만들고 싶은 그룹의 개수, 그리고 각 친구가 속할 수 있는 그룹들을 알려 줍니다. 당신의 임무는 이 목록을 받아, 각 친구가 정확히 하나의 그룹에만 속하도록 그룹을 구성하되 가장 큰 그룹의 크기를 최소화하는 프로그램을 작성하는 것입니다.

입력은 여러 개의 테스트 케이스로 이루어지며, 그 수는 최대 $20$개입니다.

각 테스트 케이스의 첫 줄에는 두 정수 $N$과 $M$이 주어집니다. $N$은 연락처 목록의 길이(친구 수), $M$은 만들고자 하는 그룹의 수입니다. 이어서 $N$개의 줄이 주어지며, 각 줄에는 한 친구의 이름과 그 친구가 속할 수 있는 그룹 번호들이 공백으로 구분되어 주어집니다.

$N$은 $1000$ 이하, $M$은 $500$ 이하라고 가정할 수 있습니다. 이름은 알파벳 문자로만 이루어지고 길이는 $15$자 이하이며, 서로 다른 두 친구가 같은 이름을 갖는 경우는 없습니다. 그룹 번호는 $0$ 이상 $M-1$ 이하의 정수입니다.

마지막 테스트 케이스 다음에는 입력의 끝을 나타내는 0 0이 한 줄로 주어집니다.

각 테스트 케이스마다, 가능한 그룹 구성 중에서 가장 큰 그룹이 가질 수 있는 최소 크기를 정수 하나로 한 줄에 출력합니다.