모그는 우즈베키스탄의 숙소에서 다른 참가자 명과 같은 방을 사용한다. 모그를 포함한 명은 처음에 모두 방 안에 있다.
방에는 열쇠가 정확히 하나 있다. 처음에 열쇠는 방 안에 있다. 문은 닫히면 자동으로 잠기므로 밖에서 열려면 열쇠가 필요하다. 하지만 방 안에 사람이 있다면 그 사람이 문을 열어 줄 수 있다.
방을 나가는 사람은 열쇠를 가지고 나가거나 방 안에 두고 갈 수 있다. 이미 방 밖에 있는 사람에게 열쇠를 전달할 수는 없다.
각 사람에게 하나 이상의 외출 일정이 주어진다. 일정 은 번 사람이 시각 에 방을 나가고 시각 에 돌아오는 일정이다. 같은 사람의 일정은 서로 겹치지 않는다. 모든 일정의 시작 시각과 종료 시각은 서로 다르다.
모그는 주어진 일정 중 일부를 선택한다. 선택된 일정만 실행하며, 선택하지 않은 일정의 주인은 그 시간에 해당 일정으로 외출하지 않는다.
일정이 끝나 돌아온 사람이 방 안에 아무도 없고 열쇠도 가지고 있지 않다면, 그 사람은 문을 열지 못하고 기다리게 된다.
어느 누구도 기다리지 않도록 열쇠를 관리할 수 있을 때, 선택할 수 있는 일정 개수의 최댓값을 구하여라.
입력은 다음과 같은 형식으로 주어진다.
각 테스트케이스마다, 아무도 기다리지 않도록 선택할 수 있는 외출 일정 개수의 최댓값을 한 줄에 하나씩 출력한다.
각 케이스는 다음과 같은 형식으로 주어진다.
번째 일정의 주인은 번 사람이며, 시작 시각과 종료 시각은 각각 , 이다. 일정은 시작 시각순으로 주어지지 않을 수 있다.
| 3 | 48 | 추가적인 제약이 없다. |
