만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

회의

면접 대비

시간 제한6초메모리 제한1024 MB

요약
각 위원이 회의 시작 시각이 속하면 참석 가능한 구간들을 제시할 때, 가장 많은 위원의 구간에 포함되는 시작 시각을 찾는다.
난이도

보통10점 중 6점

유형
정렬, 구간, 슬라이딩 윈도우, 누적 합
정답자
아직 제출이 없습니다

문제

NN명의 위원으로 구성된 이사회가 회의를 열려고 한다. 위원 수가 많아 모두가 만족하는 시간을 찾기는 어렵지만, 가능한 한 많은 사람이 참석할 수 있으면 좋겠다.

각 위원은 여러 개의 시간 구간 동안 참석 가능하며, 각 구간 [a,b][a, b]는 회의가 어떤 시각 tt (a≤t≤ba \le t \le b)에 시작하면 그 위원이 참석할 수 있다는 뜻이다. 일부 위원은 달력을 아주 엉망으로 관리해서, 한 위원이 겹치는 구간을 여러 개 줄 수도 있다. 예를 들어 [1,3][1, 3]과 [2,4][2, 4]를 줬지만 사실 [1,4][1, 4] 하나로 충분한 경우도 있다.

회의에 참석할 수 있는 위원 수의 최댓값을 구하시오.

입력

첫째 줄에는 이사회 위원 수 NN이 정수로 주어진다. (1≤N≤2⋅1051 \le N \leq 2\cdot 10^5)

이어서 NN개의 줄이 주어지며, 각 줄은 위원 한 명에 대한 것이다. ii번째 줄은 ii번째 위원이 참석할 수 있는 시간 구간의 개수 mim_i로 시작한다. (1≤mi≤2⋅1051 \leq m_i \leq 2\cdot 10^5) 그 뒤에 mim_i쌍의 정수가 이어지며, 각 쌍은 구간 하나를 나타낸다. 각 쌍 a,ba, b는 구간 [a,b][a, b]를 나타낸다. (0≤a≤b≤1090 \le a \le b \le 10^9)

B=∑i=1NmiB=\sum_{i=1}^{N} m_i를 모든 위원이 참석 가능한 시간 구간 개수의 합이라고 하자. B≤2⋅105B \leq 2\cdot 10^5이다.

출력

시작 시각을 최적으로 골랐을 때 회의에 참석할 수 있는 위원 수의 최댓값을 한 줄에 정수로 출력한다.

힌트

첫 번째 예제에서는 회의를 시각 44에 시작하면 위원 22와 33이 참석할 수 있다. 이 경우는 모든 테스트 케이스 묶음에 들어갈 수 있다.

예제 22와 33은 테스트 케이스 묶음 22나 33에는 들어갈 수 없다.

예제3

  1. 예제 1

    입력
    3
    2 1 3 5 6
    4 1 10 11 12 17 18 14 15
    1 4 4
    
    예상 출력
    2
    
  2. 예제 2

    입력
    3
    3 2 8 2 7 5 6
    4 7 15 15 20 9 13 18 20
    3 12 19 9 16 12 16
    
    예상 출력
    2
    
  3. 예제 3

    입력
    3
    2 5 14 0 20
    3 5 16 5 11 8 9
    2 7 11 7 18
    
    예상 출력
    3