Hairdresser
Petya's dad is a barber who runs a small barbershop by himself. The shop operates from 9:00 AM to 5:00 PM, but he stays until all clients who arrived before 5:00 PM are served.
Here's how the service works: If a client enters and the barber is available, the haircut begins immediately. If the barber is busy, the client waits until all previous clients are finished. The entry time of each client is logged, as well as the time when the last client leaves. To improve efficiency, the barber wants to know the minimum possible duration of the longest haircut. While it's not always possible to determine the exact duration from the logs, the barber is interested in finding the minimum time the longest haircut could have lasted. Note that every haircut takes at least five minutes. Your task is to write a program that calculates the minimum possible duration of the longest haircut based on the clients' entry times and the departure time of the last client.
Input
The first line contains the number N — the total number of clients served that day (1 ≤ N ≤ 50). The following N lines list the entry times of the clients in the format hh:mm, in the order they arrived, between 09:00 and 17:00. The final line provides the time the last client leaves the barbershop, also in hh:mm format, ranging from 09:00 to 18:59.
Output
Print the minimum possible duration of the longest haircut in minutes. The result should be accurate to within 10^{-8}. If it's impossible to serve all clients within the given timeframe, output -1.
Notes
In the first example, the longest haircut cannot be less than 90 minutes. Assume otherwise: if every haircut lasted less than 90 minutes, the second client's haircut, which ended at 17:52, must have started after 16:22. This implies the first client's haircut exceeded 7 hours, contradicting the assumption that no haircut lasts longer than 90 minutes. Thus, a 90-minute haircut is feasible.
In the last example, serving a client in one minute is impossible under the problem's conditions.