Jamie's Contact Groups

Interview

Time limit1sMemory limit128 MB

Summary

Assign each of N friends to one of M allowed groups so that every friend lands in exactly one group and the largest group size is as small as possible.

Level: Medium6 of 10
Topics: Binary search, Graph, BFS, Dynamic programming
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Examples4

Example 1

Input

3 2
John 0 1
Rose 1
Mary 1
5 4
ACM 1 2 3
ICPC 0 1
Asian 0 2 3
Regional 1 2
ShangHai 0 2
0 0

Expected output

2
2

Example 2
Input
```
1 1
Alice 0
0 0
```
Expected output
```
1
```
Example 3
Input
```
4 3
A 0
B 0
C 0
D 0
0 0
```
Expected output
```
4
```

Example 4

Input

Expected output