회의
면접 대비시간 제한6초메모리 제한1024 MB
각 위원이 회의 시작 시각이 속하면 참석 가능한 구간들을 제시할 때, 가장 많은 위원의 구간에 포함되는 시작 시각을 찾는다.
문제
명의 위원으로 구성된 이사회가 회의를 열려고 한다. 위원 수가 많아 모두가 만족하는 시간을 찾기는 어렵지만, 가능한 한 많은 사람이 참석할 수 있으면 좋겠다.
각 위원은 여러 개의 시간 구간 동안 참석 가능하며, 각 구간 는 회의가 어떤 시각 ()에 시작하면 그 위원이 참석할 수 있다는 뜻이다. 일부 위원은 달력을 아주 엉망으로 관리해서, 한 위원이 겹치는 구간을 여러 개 줄 수도 있다. 예를 들어 과 를 줬지만 사실 하나로 충분한 경우도 있다.
회의에 참석할 수 있는 위원 수의 최댓값을 구하시오.
입력
첫째 줄에는 이사회 위원 수 이 정수로 주어진다. ()
이어서 개의 줄이 주어지며, 각 줄은 위원 한 명에 대한 것이다. 번째 줄은 번째 위원이 참석할 수 있는 시간 구간의 개수 로 시작한다. () 그 뒤에 쌍의 정수가 이어지며, 각 쌍은 구간 하나를 나타낸다. 각 쌍 는 구간 를 나타낸다. ()
를 모든 위원이 참석 가능한 시간 구간 개수의 합이라고 하자. 이다.
출력
시작 시각을 최적으로 골랐을 때 회의에 참석할 수 있는 위원 수의 최댓값을 한 줄에 정수로 출력한다.
힌트
첫 번째 예제에서는 회의를 시각 에 시작하면 위원 와 이 참석할 수 있다. 이 경우는 모든 테스트 케이스 묶음에 들어갈 수 있다.
예제 와 은 테스트 케이스 묶음 나 에는 들어갈 수 없다.