문제
정올매점에서는 학생들에게 정올매점을 알리기 위하여 크리스마스날에 선물을 나누어 주기로 했다.
학생들은 각자가 좋아하는 선물이 있으며, 선물은 아무것이나 줄 수 없어서 개수가 정해져 있다.
그래서 정올매점에서는 어떻게 해야 좋을지를 알아보기로 했다.
학생들은 선물을 하나만 선택할 수 있다. 같은 선물은 없다.
따라서 1번 학생이 1번 선물을 선택하면, 2번 학생은 1번 선물을 선택할 수 없다.
머리가 좋은 수아는 이를 해결하기 위하여 학생과 선물을 하나씩 연결하기로 했다.
그런데, 어떻게 연결해야 학생들이 최대로 많은 선물을 가지고 갈까?
학생 수가 주어지고, 각 학생이 좋아하는 선물이 주어지며 또한, 정올매점에서 줄 수 있는 선물의 수가 주어질때,
학생들이 가장 많이 선물을 가지고 갈 수 있도록 연결할 때의 최대로 연결되는 수가 얼마인지 알아내어라.
입력
첫줄에 학생의 수 N(1≤N≤200)과 선물의 수 M(0≤M≤200)이 주어진다.
그 다음줄부터 N개의 줄이 나오고, 각 줄에는 다음의 수가 나온다.
각 줄의 첫번째 수 Si는 i학생이 좋아하는 선물의 개수 이며,
그 다음 수는 Si개 만큼 i학생이 좋아하는 선물의 번호가 나온다.
Si의 범위는 0≤Si≤M이고, 상품의 번호는 1부터 M까지이다.
출력
학생들이 가장 많이 선물을 가지고 갈 수 있도록 연결할 때의 최대로 연결되는 수를 출력한다.
예제1
입력
55
225
3234
215
3125
12
출력
4
출처
USACO 40, poj 1274