Welcome to ZOJ
55 - ZOJ Monthly, September 2006 - 1003

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Mr. Smith is writing a program of a movie player. His player supports subtitles and he wants to create a new format of subtitle files. The new format looks like this:

This is the first text line.
The time-tag of this line can be omitted.
A text line will not be empty.

Each text line has a time-tag above it. A time-tag has a form of "HH:MM:SS.CC" (HH for hours, MM for minutes, SS for seconds and CC for centiseconds). The whole file will be ended with a line of "END" (it is just for denoting the end of file, and won't be displayed).

However, Mr. Smith finds that some of the time-tags can be omitted. We choose any two of the time-tags, and then, if all the time-tags between them can be calculated in the range of error with the two time-tags, all the time-tags between them can be omitted. For instance, the second time-tag in the example above can be omitted with an error range of -5 centiseconds to +5 centiseconds. You can see that the lengths of the first text line and the second one are 28 and 41, and the first time-tag and the third one are 0 centisecond and 300 centisecond, so the second time-tag should be 0 + (300 - 0) * 28 / (28 + 41) = 121.739 averagely, rounding to the nearest integer 122. Because the second time-tag is 125 centisecond actually and 122 - 5 = 117 <= 125 <= 127 = 122 + 5, it can be omitted. And of course the first and the last time-tags cannot be omitted.

Write a program to count how many time-tags can be omitted at most.


There are several test cases. In each test case, the first line contains one integer E (0 <= E <= 100) which is the error range in centiseconds, and then the subtitle file follows. In each two of the following lines, the first line is the time-tag and the second one is the subtitle text. A text line of "END" denotes the end of the subtitle file. The number of the time-tags in a subtitle file won't exceed 1000. The length of a text line is at most 100 and at least 1. You can assume that the time-tags are in nondecreasing order. E = -1 denotes the end of input.


For each test case, output one line with the maximum number of time-tags that can be omitted in the error range of -E centiseconds to +E centiseconds.

Sample Input

The first line
The second line
The third line
The fourth line

Sample Output



The second and the third time-tags can be omitted by being calculated with the first and the fourth time-tags.

Author: JIAN, Hengyi

Submit    Status