시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 241 | 78 | 58 | 34.320% |
학생들은 지금 치르고 있는 모의고사가 마지막일 것으로 생각하고 있겠지만, 모의고사가 끝난 뒤에는 사실 마지막 조별 시합이 있다. 마지막 조별 시합에서는 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