MPART - Group Partition

Giới hạn

• Thời gian: 6.752s
• Bộ nhớ: 1536MB
• Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

Phân người vào các nhóm sao cho nhóm có nhiều người nhất có số lượng người ít nhất có thể.

Input

Có không quá 20 test. Dòng đầu mỗi test là hai số N,M : N số người, M số nhóm.

N dòng tiếp theo, đầu tiên là tên người, sau đó là danh sách các nhóm mà người đó có thể được phân vào (1<=N<=1000,M<=500).

Tên người chỉ gồm kí tự chữ cái và có độ dài <=15 , không có 2 người trùng tên. Mã nhóm đánh số từ 0 cho đến M-1.

Kết thúc test là hai số 0 0.

Sample 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 

Output

Hiện ra số người của nhóm mà nhiều người nhất mà thỏa mãn điều kiện trên.

Sample output

2
2

---

• Người up: vdmedragon
• Nguồn bài: Shanghai 2004