Jamie's Contact Groups

Jamie is a very popular girl and has quite a lot of friends, so she always keeps a very long contact list on her phone. The list has grown so long that it often takes her a long time to browse through the whole thing to find a friend's number. As Jamie's best friend and a programming genius, you suggest that she split the contact list into groups and minimize the size of the largest group, so that it becomes much easier to search for a friend's number within a group.

Jamie takes your advice and gives you the full list of her friends' names, the number of groups she wants, and the groups each friend could belong to. Your task is to write a program that organizes the list into groups so that each friend belongs to exactly one group and the size of the largest group is minimized.

The input consists of several test cases; there are at most $20$ of them.

Each test case starts with a line containing two integers $N$ and $M$, where $N$ is the length of the contact list (the number of friends) and $M$ is the number of groups. Then $N$ lines follow, each containing a friend's name and the group numbers that friend could belong to, separated by spaces.

You may assume that $N$ is no more than $1000$ and $M$ is no more than $500$. Names contain alphabet letters only and are no longer than $15$ characters, and no two friends share the same name. Each group label is an integer between $0$ and $M-1$, inclusive.

After the last test case, a single line 0 0 terminates the input.

For each test case, output a single line containing one integer: the smallest possible size of the largest group over all valid groupings.