Restaurants#453
There is a restaurant chain in a certain city with a total of nearly identical halls. The administration has received applications for holding corporate events on the eve of a holiday. Each application specifies the start and end time (from 00\!:\!00 to 23\!:\!59). Each event requires an entire hall (it does not matter which one). After an event ends, at least half an hour is needed to prepare the hall for the next event. The task is to accommodate the maximum possible number of applications. If it is possible to satisfy all applications, then the minimum possible number of halls should be used.
The first line contains the numbers and (1 \leq N, K \leq 100). Each of the following lines contains the start and end time of the application in the format HH\!:\!MM-HH\!:\!MM. The end time of each application is at least one minute later than its start time.
The first line should contain two numbers: the number of satisfied applications , and the number of halls used. Each of the next lines should contain two numbers: the index of the application (as it appears in the input file) and the hall number. If there are several possible solutions, output any one of them.
Example 1