시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB241785834.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까지의 정수로 나타낸다.

출력

첫째 줄에 답을 출력한다.

예제 입력 1

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

예제 출력 1

5
W3sicHJvYmxlbV9pZCI6IjIxMjgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI5YzhcdWM5YzBcdWI5YzkgXHVjODcwXHViY2M0IFx1YzJkY1x1ZDU2OSIsImRlc2NyaXB0aW9uIjoiPHA+XHVkNTU5XHVjMGRkXHViNGU0XHVjNzQwIFx1YzljMFx1YWUwOCBcdWNlNThcdWI5NzRcdWFjZTAgXHVjNzg4XHViMjk0IFx1YmFhOFx1Yzc1OFx1YWNlMFx1YzBhY1x1YWMwMCBcdWI5YzhcdWM5YzBcdWI5YzlcdWM3N2MgXHVhYzgzXHVjNzNjXHViODVjIFx1YzBkZFx1YWMwMVx1ZDU1OFx1YWNlMCBcdWM3ODhcdWFjYTBcdWM5YzBcdWI5Y2MsIFx1YmFhOFx1Yzc1OFx1YWNlMFx1YzBhY1x1YWMwMCBcdWIwNWRcdWIwOWMgXHViNGE0XHVjNWQwXHViMjk0IFx1YzBhY1x1YzJlNCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjODcwXHViY2M0IFx1YzJkY1x1ZDU2OVx1Yzc3NCBcdWM3ODhcdWIyZTQuIFx1YjljOFx1YzljMFx1YjljOSBcdWM4NzBcdWJjYzQgXHVjMmRjXHVkNTY5XHVjNWQwXHVjMTFjXHViMjk0IEFcdWM4NzBcdWM2NDAgQlx1Yzg3MFx1Yzc1OCBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1Yzg3MFx1Yjg1YyBcdWIwOThcdWIyNThcdWM1YjQgXHVjMmRjXHVkNTY5XHVjNzQ0IFx1ZDU1OFx1YWM4YyBcdWI0MThcdWIyOTRcdWIzNzAsIFx1Yzc3NFx1YmM4OFx1YzVkMFx1YjI5NCBcdWFjMDEgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzc0IFx1Yzc5OCBcdWQ0NzhcdWIyOTQgXHVjNTRjXHVhY2UwXHViOWFjXHVjOTk4IFx1YmIzOFx1YzgxY1x1YzVkMCBcdWI1MzBcdWI3N2NcdWMxMWMgXHVjODcwXHViOTdjIFx1YjA5OFx1YjIwNFx1YWUzMFx1Yjg1YyBcdWQ1NThcdWM2MDBcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc0MCBcdWNkMWQgTigxICZsZTsgTiAmbGU7IDEsMDAwKVx1YmE4NVx1Yzc3NCBcdWM3ODhcdWFjZTAsIFx1YzU0Y1x1YWNlMFx1YjlhY1x1Yzk5OCBcdWJiMzhcdWM4MWNcdWM3NTggXHVjODg1XHViOTU4XHViMjk0IEQoMSAmbGU7IEQgJmxlOyAxNSlcdWM4ODVcdWI5NThcdWM3NzRcdWIyZTQuIFx1Yzg3MFx1Yjk3YyBcdWIwOThcdWIyMGMgXHViNTRjXHVjNWQwXHViMjk0IFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc1OCBcdWM4MTBcdWMyMThcdWFjMDAgXHVjNWI0XHViMjkwIFx1YzgxNVx1YjNjNFx1YWMwMCBcdWI0MThcdWIzYzRcdWI4NWQgXHVkNTc0XHVjNTdjIFx1ZDU1OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIEFcdWM4NzAgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzc0IFx1ZDQ4MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHViYjM4XHVjODFjXHViNGU0XHVjNzU4IFx1Y2QxZCBcdWFjMDBcdWM5ZDNcdWMyMThcdWFjMDAgSygxICZsZTsgSyAmbGU7IEQpXHVhYzFjIFx1Yzc3NFx1ZDU1OFx1YWMwMCBcdWI0MThcdWIzYzRcdWI4NWQgXHVkNTU4XHViODI0IFx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1YWUzMFx1YzkwMFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIzYzRcdWI4NWQgQVx1Yzg3MFx1Yjk3YyBcdWJmNTFcdWFjZTAsIFx1YjA5OFx1YmEzOFx1YzljMCBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NDQgQlx1Yzg3MFx1YzVkMCBcdWIxMjNcdWM3M2NcdWI4MjQgXHVkNTVjXHViMmU0LiBcdWM4NzBcdWJjYzQgXHVjMmRjXHVkNTY5XHVjNWQwXHVjMTFjXHViMjk0IFx1Yzg3MFx1YmNjNCBcdWQxYTBcdWI4NjAgXHVjMmRjXHVhYzA0XHVjNzc0IFx1Yzc4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YWRmOCBcdWM4NzBcdWM1ZDAgXHVjNzg4XHViMjk0IFx1ZDU1OVx1YzBkZFx1YjRlNCBcdWM5MTEgXHVkNTVjIFx1YmE4NVx1Yzc3NFx1Yjc3Y1x1YjNjNCBcdWJiMzhcdWM4MWNcdWI5N2MgXHVkNDgwIFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJhNzQgXHViMDk4XHViYTM4XHVjOWMwIFx1ZDU1OVx1YzBkZFx1YjRlNFx1YjNjNCBcdWJiMzhcdWM4MWNcdWI5N2MgXHVkNDgwIFx1YzIxOCBcdWM3ODhcdWFjOGMgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWI3ZWNcdWQ1NWMgXHVjODcwXHVhYzc0XHVjNzNjXHViODVjXHViMjk0IEFcdWM4NzBcdWM2NDAgQlx1Yzg3MFx1Yzc1OCBcdWM2YjBcdWM1ZjRcdWM3NDQgXHViYzE0XHViODVjIFx1YzU0Y1x1YWUzMCBcdWQ3OThcdWI0ZTRcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWM2YjBcdWMxMjAgQVx1Yzg3MFx1YWMwMCBcdWNkNWNcdWIzMDAgXHViYTg3IFx1YmE4N1x1YWU0Y1x1YzljMCBcdWFjMDBcdWIyYTVcdWQ1NWNcdWM5YzBcdWI5N2MgXHVjNTRjXHVjNTQ0XHViY2Y0XHViODI0IFx1ZDU1Y1x1YjJlNC4gXHVkNTU5XHVjMGRkXHViNGU0XHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgQVx1Yzg3MFx1Yzc1OCBcdWNkNWNcdWIzMDAgXHVjNzc4XHVjNmQwXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWMxMzggXHVjODE1XHVjMjE4IE4sIEQsIEtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjYzI4XHViODQwXHViODVjIDFcdWJjODggXHVkNTU5XHVjMGRkXHViZDgwXHVkMTMwIE5cdWJjODggXHVkNTU5XHVjMGRkXHVhZTRjXHVjOWMwXHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWM5MDRcdWM3NTggXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM4MTVcdWMyMThcdWIyOTQgXHVhZGY4IFx1ZDU1OVx1YzBkZFx1Yzc3NCBcdWQ0ODAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM1NGNcdWFjZTBcdWI5YWNcdWM5OTggXHViYjM4XHVjODFjXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yzc3NFx1YWNlMCwgXHViMmU0XHVjNzRjXHVjNWQwXHViMjk0IFx1YWRmOCBcdWQ1NTlcdWMwZGRcdWM3NzQgXHVkNDgwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjNTRjXHVhY2UwXHViOWFjXHVjOTk4IFx1YmIzOFx1YzgxY1x1YjRlNFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM1NGNcdWFjZTBcdWI5YWNcdWM5OTggXHViYjM4XHVjODFjXHViNGU0XHVjNzU4IFx1YmM4OFx1ZDYzOFx1YjI5NCAxXHViZDgwXHVkMTMwIERcdWFlNGNcdWM5YzBcdWM3NTggXHVjODE1XHVjMjE4XHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjJmNVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjEyOCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkRpc2Vhc2UgTWFuYWdlbWVudCIsImRlc2NyaXB0aW9uIjoiPHA+QWxhcyEgQSBzZXQgb2YgRCAoMSAmbHQ7PSBEICZsdDs9IDE1KSBkaXNlYXNlcyAobnVtYmVyZWQgMS4uRCkgaXMgcnVubmluZyB0aHJvdWdoIHRoZSBmYXJtLiBGYXJtZXIgSm9obiB3b3VsZCBsaWtlIHRvIG1pbGsgYXMgbWFueSBvZiBoaXMgTiAoMSAmbHQ7PSBOICZsdDs9IDEsMDAwKSBjb3dzIGFzIHBvc3NpYmxlLiBJZiB0aGUgbWlsa2VkIGNvd3MgY2FycnkgbW9yZSB0aGFuIEsgKDEgJmx0Oz0gSyAmbHQ7PSBEKSBkaWZmZXJlbnQgZGlzZWFzZXMgYW1vbmcgdGhlbSwgdGhlbiB0aGUgbWlsayB3aWxsIGJlIHRvbyBjb250YW1pbmF0ZWQgYW5kIHdpbGwgaGF2ZSB0byBiZSBkaXNjYXJkZWQgaW4gaXRzIGVudGlyZXR5LiBQbGVhc2UgaGVscCBkZXRlcm1pbmUgdGhlIGxhcmdlc3QgbnVtYmVyIG9mIGNvd3MgRkogY2FuIG1pbGsgd2l0aG91dCBoYXZpbmcgdG8gZGlzY2FyZCB0aGUgbWlsay48XC9wPlxyXG4iLCJpbnB1dCI6Ijx1bD5cclxuXHQ8bGk+TGluZSAxOiBUaHJlZSBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnM6IE4sIEQsIGFuZCBLPFwvbGk+XHJcblx0PGxpPkxpbmVzIDIuLk4rMTogTGluZSBpKzEgZGVzY3JpYmVzIHRoZSBkaXNlYXNlcyBvZiBjb3cgaSB3aXRoIGEgbGlzdCBvZiAxIG9yIG1vcmUgc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzLiBUaGUgZmlyc3QgaW50ZWdlciwgZF9pLCBpcyB0aGUgY291bnQgb2YgY293IGkmIzM5O3MgZGlzZWFzZXM7IHRoZSBuZXh0IGRfaSBpbnRlZ2VycyBlbnVtZXJhdGUgdGhlIGFjdHVhbCBkaXNlYXNlcy4gT2YgY291cnNlLCB0aGUgbGlzdCBpcyBlbXB0eSBpZiBkX2kgaXMgMC48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6Ijx1bD5cclxuXHQ8bGk+TGluZSAxOiBNLCB0aGUgbWF4aW11bSBudW1iZXIgb2YgY293cyB3aGljaCBjYW4gYmUgbWlsa2VkLjxcL2xpPlxyXG48XC91bD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==