Informatica Online Judge

  사진찍는 사감선생님 [0641 / 0281]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 4   Total Tried : 15


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[]

Background

GSHS의 사감 선생님은 게임을 하는 학생을 잡아낼 새로운 방법을 개발했다.

바로 학생들이 게임을 하는 사진을 찍어서 증거자료로 쓰는 것이다.

이렇게 되면 사감 선생님이 뒤에 왔을 때 게임을 끄고 시치미를 떼는 방법이 통하지 않기 때문이다. 한편, 당신은 불행하게도 게임을 하는 모습이 카메라에 포착당해 퇴사의 위기에 처했다.

이 때 당신은 사감 선생님을 도와줄 프로그램을 작성하고 퇴사를 면하고자 사감 선생님과 거래를 하게 되는데, n명의 학생들이 게임을 하는 시간이 0시부터 24시 사이의 구간으로 주어지고 사감 선생님이 사진을 찍은 뒤 정리하는 시간 m이 주어진다.

이 말은 사감 선생님이 2시에 게임을 하는 학생의 사진을 찍고 나서 m=3일 때 다음 사진은 5시부터 찍을 수 있다는 뜻이다.

같은 학생이 게임을 하는 모습을 3번 찍혔을 때 그 학생은 퇴사당하는데, 0시부터 24시까지 하루 동안 n명의 학생들 중 (1<=n<=5) 사감 선생님이 가능한 한 많이 퇴사시킬 수 있는 학생의 수를 구하는 프로그램을 짜야 된다.

Input

1번째 줄에는 학생의 수 n과 사감 선생님이 사진을 찍고 정리하는 시간 m(1<=m<=24)이 주어진다.

2번째 줄부터 n+1번째 줄까지는 한 학생의 게임을 하는 시간대의 수 k(1<=k<=24), 그리고 이후 같은 줄에 k개만큼 게임을 하는 시간대의 시작점과 끝점이 주어진다. (0<=시작점<=끝점<=24)

Output

사감 선생님이 최대한 퇴사시킬 수 있는 학생의 수를 출력하시오.

IO Example

입력
5 1
2 0 1 19 21
1 19 24
2 16 18 19 21
3 12 13 16 17 21 22
1 22 24

출력
4

* 설명 : 첫 번째 줄의 입력은 학생은 총 5명, 사감 선생님의 사진 정리시간은 1 예를 들어 3시에 사진을 찍는다면 4시부터 다음 사진을 찍을 수 있다.는 의미이다.
두 번째 줄부터 주어진 데이터의 첫 번째 값은 게임을 하는 구간의 수 이고 다음 데이터 들은 구간의 시작값과 끝값이다.

예를 들어 2 0 1 19 21이라면 구간의 수는 2개 각 구간은 0~1시 구간과 19~21시 구간에 게임을 한다는 의미이다.

위 첫 번째 예시는 0시에 학생 1의 1번째 사진을 찍는다. 1시에 학생 1의 2번째 사진을 찍는다. 12시에 학생 4의 1번째 사진을 찍는다. 13시에 학생 4의 2번째 사진을 찍는다. 16시에 학생 4의 3번째 사진을 찍는다. (학생4 퇴사, 현재 퇴사 학생수 1) 17시에 학생 3의 1번째 사진을 찍는다. 18시에 학생 3의 2번째 사진을 찍는다. 19시에 학생 3의 3번째 사진을 찍는다. (학생3 퇴사, 현재 퇴사 학생수 2) 20시에 학생 1의 3번째 사진을 찍는다. (학생1 퇴사, 현재 퇴사 학생수 3) 22시에 학생 5의 1번째 사진을 찍는다. 23시에 학생 5의 2번째 사진을 찍는다. 24시에 학생 5의 3번째 사진을 찍는다. (학생5 퇴사, 현재 퇴사 학생수 4)

입력2
3 3
2 8 12 15 18
2 15 16 18 22
1 17 24

출력
2

* 설명 : 8시에 학생 1의 1번째 사진을 찍는다. 11시에 학생 1의 2번째 사진을 찍는다. 15시에 학생 1의 3번째 사진을 찍는다. (학생1 퇴사, 현재 퇴사 학생수 1) 18시에 학생 3의 1번째 사진을 찍는다. 21시에 학생 3의 2번째 사진을 찍는다. 24시에 학생 3의 3번째 사진을 찍는다. (학생3 퇴사, 현재 퇴사 학생수 2)

출제 : 안성현(GSHS-29th, 2012알고리즘수행평가)

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]