In a certain city there is a restaurant network that has a total of n almost identical halls. The administration received k applications for holding corporate events on a pre-holiday day. Each application specifies the start and end time (from 00:00 to 23:59). To carry out one event, one hall is needed entirety (which specifically does not matter). After the end of the event, you need at least half an hour to prepare for the next event in this room. It is required to satisfy as many applications as possible. If you can satisfy all, then the smallest number of halls should be used.

Input

First line contains the numbers n and k (1 ≤ n, k ≤ 100). Each of the next k lines contains the starting and ending time of application in the form HH:MM-HH:MM. The end time of each application is at least one minute longer than the start time.

Output

Print in one line two numbers - the number of applications p that is possible to satisfy and the number of halls q to use.