시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 227 75 67 42.138%

문제

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

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

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

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

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

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

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

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

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

입력

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

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

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

출력

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

예제 입력 1

3 3 10
1 20
1
1 10
2
1 0
3

예제 출력 1

4