시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 429 66 17 5.397%

문제

정인이는 Top Root호텔에서 예약을 관리하는 일을 하고 있다. 오늘 정인이는 호텔 예약을 관리하는 소프트웨어에서 버그를 발견했다. 이 버그로 인해서 방이 겹치게 예약되고 잘못 배정되는 일이 발생했다. 이 소프트웨어를 만든 회사는 이미 망해버렸다. 따라서, 정인이는 자신이 직접 버그를 고치고 대책을 세우기로 했다.

먼저, 정인이는 예약 정보를 모두 내보냈다. 이 정보에는 예약 코드와 입실 시간, 퇴실 시간이 적혀져 있다. 이 정보를 이용해서 방을 배정하려면 방이 적어도 몇 개나 필요한지 구하는 프로그램을 작성하시오. 방은 다시 사용하기 전에 반드시 청소되어야 한다. 정인이는 위험을 감수하지 않으려고 한다. 따라서, 방을 청소하는 시간은 항상 최대 청소 시간과 같다.

입력

입력은 여러 줄로 이루어져 있다. 첫째 줄에는 테스트 케이스의 개수 1 ≤ T ≤ 100가 주어진다. 각 테스트 케이스의 첫째 줄에는 예약의 수 1 ≤ B ≤ 5000와 한 방을 청소하는데 걸리는 시간 0 ≤ C ≤ 360가 주어진다. 청소 시간의 단위는 분이다.

다음 B개 줄에는 각 예약의 정보가 주어진다. 예약 정보는 예약 코드와 입실 시간, 퇴실 시간으로 이루어져 있다. 예약 코드는 알파벳과 숫자로만 이루어져 있으며, 최대 20글자이다. 날짜는 "YYYY-MM-DD HH:MM" 형식이고, 2013년부터 2016년 사이의 예약만 주어진다.

출력

각 테스트 케이스에 대해서, 필요한 방의 최소 개수를 출력한다. 윤년에 유의해서 문제를 풀어야 한다. 또, 일광 절약 시간제 (Daylight saving time)는 고려하지 않아도 된다. 

예제 입력

4
2 120
1 2013-07-01 15:59 2013-07-08 16:30
2 2013-07-08 17:30 2013-07-15 12:00
3 60
65 2013-07-08 14:30 2013-07-08 16:00
32 2013-07-01 16:00 2013-07-15 12:00
91 2013-07-01 16:00 2013-07-08 15:00
2 360
a7 2016-02-21 14:00 2016-02-28 21:00
xx 2016-03-01 01:00 2016-03-02 12:57
2 60
a9 2016-02-21 14:00 2016-02-28 11:00
a8 2016-02-28 12:00 2016-03-11 21:00

예제 출력

2
3
1
1

힌트