14572번 - 스터디 그룹

신입생 현우는 알고리즘 공부가 정말 재밌다.

현우는 이번에 스터디 그룹을 만들어 더욱 열심히 공부해보려 한다.

하지만 사공이 많으면 배가 산으로 간다고, 그룹에 참여하는 학생이 너무 많을 경우 지지부진한 결과가 나오게 될 것을 우려한 현우는 아래와 같은 조건을 내걸었다.

그룹 내에서 가장 잘 하는 학생과 가장 못 하는 학생의 실력 차이가 D 이하여야 한다.

또한, 그룹의 효율성 E를 아래와 같이 정의하였다.

E = (그룹 내의 학생들이 아는 모든 알고리즘의 수 - 그룹 내의 모든 학생들이 아는 알고리즘의 수) * 그룹원의 수

현우는 위와 같은 두 가지 조건을 체크하기 위해, 모든 학생들의 실력을 수치화하고, 중요한 알고리즘 K개에 대해, 각 학생들이 어떤 알고리즘을 알고 있는지를 모두 조사하였다.

현우는 조건을 만족하는 학생들의 부분집합 중 효율성이 최대가 되는 그룹을 뽑아 스터디 그룹으로 만들 생각이다.

현우가 만들 스터디 그룹의 효율성은 얼마가 될까?

첫 줄에 학생의 수 N, 알고리즘의 수 K, 문제에 설명한 D가 주어진다. (1 ≤ N ≤ 10⁵, 1 ≤ K ≤ 30, 0 ≤ D ≤ 10⁹)

이어 N명의 학생에 대한 정보가 아래와 같이 주어진다.

• M d (0 ≤ M ≤ K, 0 ≤ d ≤ 10⁹): 해당 학생이 알고 있는 알고리즘의 수, 해당 학생의 실력
• 다음 줄에, M개의 정수 A_i: 해당 학생이 알고 있는 알고리즘들 (1 ≤ A_i ≤ K)

가장 효율성이 높은 그룹의 효율성을 출력한다.