시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 12 6 6 54.545%

문제

학생들은 지금 치르고 있는 모의고사가 마지막일 것으로 생각하고 있겠지만, 모의고사가 끝난 뒤에는 사실 마지막 조별 시합이 있다. 마지막 조별 시합에서는 A조와 B조의 두 개의 조로 나뉘어 시합을 하게 되는데, 이번에는 각 학생들이 잘 푸는 알고리즘 문제에 따라서 조를 나누기로 하였다.

학생들은 총 N(1≤N≤1,000)명이 있고, 알고리즘 문제의 종류는 D(1≤D≤15)종류이다. 조를 나눌 때에는 학생들의 점수가 어느 정도가 되도록 해야 하기 때문에, A조 학생들이 풀 수 있는 서로 다른 문제들의 총 가짓수가 K(1≤K≤D)개 이하가 되도록 하려 한다. 이 기준을 만족하도록 A조를 뽑고, 나머지 학생들을 B조에 넣으려 한다. 조별 시합에서는 조별 토론 시간이 있기 때문에, 그 조에 있는 학생들 중 한 명이라도 문제를 풀 수 있으면 나머지 학생들도 문제를 풀 수 있게 된다.

이러한 조건으로는 A조와 B조의 우열을 바로 알기 힘들기 때문에, 우선 A조가 최대 몇 몇까지 가능한지를 알아보려 한다. 학생들에 대한 정보가 주어졌을 때, A조의 최대 인원수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 세 정수 N, D, K가 주어진다. 다음 N개의 줄에는 차례로 1번 학생부터 N번 학생까지의 정보가 주어진다. 각 줄의 첫 번째 정수는 그 학생이 풀 수 있는 알고리즘 문제의 개수이고, 다음에는 그 학생이 풀 수 있는 알고리즘 문제들의 번호가 주어진다. 알고리즘 문제들의 번호는 1부터 D까지의 정수로 나타낸다.

출력

첫째 줄에 답을 출력한다.

예제 입력

6 3 2
0
1 1
1 2
1 3
2 2 1
2 2 1

예제 출력

5

힌트