Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
55 - ZOJ Monthly, September 2006 - 1003
Subtitle

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:

00:00:00.00
This is the first text line.
00:00:01.25
The time-tag of this line can be omitted.
00:00:03.00
A text line will not be empty.
00:00:10.00
END

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.

Input

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.

Output

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

5
00:00:00.00
The first line
00:00:01.25
The second line
00:00:02.75
The third line
00:00:04.00
The fourth line
00:00:05.00
END
-1

Sample Output

2

Hint

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