아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Mötet

면접 대비

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

요약
각 위원이 여러 개의 가능 시간 구간을 주는데, 가장 많은 위원이 참석할 수 있는 시작 시각을 찾는다.
난이도

보통10점 중 5점

유형
구간, 정렬, 누적 합
정답자
아직 제출이 없습니다

문제

En styrelse med NN medlemmar planerar att ha ett möte. På grund av det stora antalet styrelseledamöter är det svårt att hitta en tid som passar alla, men man vill gärna att så många personer som möjligt kan vara med på mötet.

Varje ledamot är tillgänglig under ett antal olika tidsintervall, där varje tidsintervall \[a,b]\[a, b] betyder att ledamöten kan närvara om mötet startar vid någon tid tt där a≤t≤ba \le t \le b. Eftersom vissa ledamöter är väldigt slarviga med sina kalendrar kan en och samma ledamot råka ge dig olika tidsintervall som överlappar, t.ex \[1,3]\[1, 3] och \[2,4]\[2, 4], även om det haed räckt med ett enda intervall, i detta fall \[1,4]\[1, 4].

Beräkna det största antalet ledamöter som kan delta på mötet.

입력

Den första raden innehåller ett heltal NN (1≤N≤2⋅1051 \le N \leq 2\cdot 10^5), antalet ledamöter i styrelsen.

Därefter följer NN rader, en för varje styrelseledamot. Den ii:te raden börjar med antalet tidsintervall m_im\_i (1≤m_i≤2⋅1051 \leq m\_i \leq 2\cdot 10^5) som den ii:te ledamöten kan närvara under. Detta följs av m_im\_i par av heltal, ett för varje intervall. Dessa par a,ba, b (0≤a≤b≤1090 \le a \le b \le 10^9) representerar intervallet \[a,b]\[a, b].

Låt B=∑_i=1Nm_iB=\sum\_{i=1}^{N} m\_i vara summan av antalet tidsintervall som alla ledamöter är tillgängliga under. Då gäller det att B≤2⋅105B \leq 2\cdot 10^5.

출력

Skriv ut en rad med ett heltal -- det största antalet ledamöter som kan delta i mötet om starttiden väljs optimalt.

힌트

I det första exemplet kan vi välja att starta mötet vid tiden 44, då ledamot 22 och 33 kan delta. Fallet skulle kunna vara med i samtliga testfallsgrupper.

Exempel 22 och 33 skulle inte kunna förekomma i testfallsgrupp 22 eller 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