402184: GYM100687 J ACM Student Chapter (B)

One day, Dr. Ibrahim noticed that some questions were answered after 3 hours and decided to increase the number ACM admins that answer questions on the group.

ACM admins are really good at Structured Programming. It takes any admin exactly 15 minutes to answer any question, but they can’t answer more than one question at the same time. For example, if an admin starts working on a question at time 03:00:00, he will answer at time 03:14:59 and will be free to start working on another question at 03:15:00 or later.

Given the summary of the posts of one day, find the minimum number of admins required to answer all the questions, such that each question is answered within 3 hours.

The first line of input contains an integer N (1 ≤ N ≤ 100,000) representing the number of questions.

Each of the following N lines contains the time at which one of the questions was posted.

The format of the time is: HH:MM:SS (00 ≤ HH ≤ 23), (00 ≤ MM, SS ≤ 59). Note that all of the given data is within one day, but not necessarily sorted. All questions must be answered within 3 hours even if it was posted at 23:59:59 (in this case, the answer will be in the next day).

Print the minimum number of admins Dr. Ibrahim has to assign so that all the questions are answered within 3 hours.

3
03:22:15
00:42:08
18:49:22

1