스터디 그룹

• 효율성 공식에 따르면, 그룹이 커질수록 효율성도 항상 커진다. {A,B가 아는 모든 알고리즘의 수} ≤ {A,B,C가 아는 모든 알고리즘의 수}이고 {A,B가 모두 아는 알고리즘의 수} ≥ {A,B,C가 모두 아는 알고리즘의 수} 이므로 당연한 이야기이다.
• 따라서, 가장 실력이 낮은 사람이 X인 그룹중에서 효율성이 가장 큰 그룹은, 실력이 X이상 X+D이하인 모든 사람이 포함되어있는 그룹이다.
• 이러한 그룹들은, 학생들을 실력순으로 정렬한 배열에서 부분배열로 등장한다. 투 포인터를 이용하면 O(n)에 실력차가 D에 가까운 부분배열들을 모두 포함하면서 탐색할 수 있다. left와 right를 유지하면서 right와 left의 실력차이가 D보다 작으면 right를 증가시키고, D보다 크면 left를 증가시키는 방식으로 탐색하면 된다.
• 또한 모든 알고리즘에 대해서 그룹내에 그 알고리즘을 알고있는 사람의 수를 유지하면 이것으로부터 {그룹 내의 학생들이 아는 모든 알고리즘의 수 - 그룹 내의 모든 학생들이 아는 알고리즘의 수}를 O(K)에 계산 가능하다. 갱신하는 것도 O(K)에 가능한데, right가 증가할때, 즉 그룹에 한명이 추가될때는, 추가되는 사람이 알고있는 알고리즘들에 대해서 카운트를 1씩 증가시키고, left가 증가할때 (=그룹에서 한명을 제외시킬때)에는 제외되는 사람이 알고있는 알고리즘들에 대해서 카운트를 1씩 줄인다.
• 따라서 한번 포인터를 움직일때마다 O(K)의 알고리즘 카운트 갱신과 O(K)의 효율성 계산이 필요하고, 포인터는 총 O(N)번 움직이면 되므로, 총 시간복잡도는 O(NK).

"""Solution code for "BOJ 14572. 스터디 그룹".

- Problem link: https://www.acmicpc.net/problem/14572
- Solution link: http://www.teferi.net/ps/problems/boj/14572

Tags: [TwoPointer]
"""

import sys
import typing


class Student(typing.NamedTuple):
    level: int
    algorithms: list[int]


def main():
    N, K, D = [int(x) for x in sys.stdin.readline().split()]
    students = []
    for _ in range(N):
        # pylint: disable=unused-variable
        M, d = [int(x) for x in sys.stdin.readline().split()]
        A = [int(x) for x in sys.stdin.readline().split()]
        students.append(Student(d, A))

    students.sort()
    answer = 0
    known_count_by_algo = [0] * K
    left_iter = iter(students)
    left = next(left_iter)
    group_size = 0
    for right in students:
        group_size += 1
        for algo in right.algorithms:
            known_count_by_algo[algo - 1] += 1
        while right.level - left.level > D:
            for algo in left.algorithms:
                known_count_by_algo[algo - 1] -= 1
            left = next(left_iter)
            group_size -= 1
        E = group_size * sum(1 for known_count in known_count_by_algo
                             if 0 < known_count < group_size)
        answer = max(answer, E)

    print(answer)


if __name__ == '__main__':
    main()