시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초 1024 MB70412455.814%

문제

주행을 마친 버스들이 종점에 들어온다. 종점에 들어온 버스는 버스를 정비하기 위한 자리에 들어간다. 즉, 종점에 버스 4대가 있다면 버스를 정비할 수 있는 공간이 최소 4개 이상 필요하다. 만약 같은 시각에 종점에 들어오는 버스 A와 종점에서 출발하는 버스 B가 있을 경우는 버스 B가 먼저 종점에서 출발하고 그 다음으로 버스 A가 종점으로 들어온다.

버스의 시간표가 매일 동일하며 종점에 들어오는 시각과 나가는 시각이 매일 동일하다.

이번에 버스 시간표가 변경이 되어 버스를 정비하는 공간이 최소 몇 개 이상 필요한지 다시 계산을 해야한다. 이를 도와 계산을 해주자.

입력

첫 번째 줄에는 종점에 들어오는 버스들의 개수 $N$이 주어진다.

두 번째 줄부터 $N+1$번째 줄까지 각 버스가 종점에 들어오는 시각과 종점에서 나가는 시각이 주어진다.

주어지는 시각의 형식은 다음과 같다. HH:MM:SS.sss (HH는 시각을, MM은 분, SS은 초, sss 밀리초를 의미한다.)

출력

버스 정비를 위한 공간이 최소 몇 개 이상 필요한지 출력한다.

제한

  • $1 ≤ N ≤ 100,000$
  • $0 ≤ HH < 24$
  • $0 ≤ MM < 60$
  • $0 ≤ SS < 60$
  • $0 ≤ sss < 1000$

예제 입력 1

4
06:00:00.000 06:30:00.000
06:10:45.000 06:15:00.000
06:30:00.000 06:40:00.000
06:01:00.001 06:40:00.001

예제 출력 1

3

출처