Problem Description

Moon is preparing for the beginning-of-term exam on computer networks and is reviewing knowledge about switches. A switch has an amazing feature: its table is built automatically, dynamically, and autonomously, meaning there is no intervention from a network administrator or any configuration protocol. In other words, the switch is self-learning. This ability is roughly implemented in the following way:

1. The switch table is initially empty.
2. For every frame received on each interface, the switch stores the source $\text{MAC}$ address of the frame in its table.
3. If, after a period of time (called the aging time), the switch does not receive any frame containing a certain source $\text{MAC}$ address, it deletes that source $\text{MAC}$ address from the table.

Now you are given all frames received by a switch during one day (each frame contains a source $\text{MAC}$ address and the arrival time of the frame). Please help Moon compute the minimum number of entries the switch table needs during that day, so that the information of all frames can be stored. Note: for simplicity, at each time point, perform deletions first and then insertions.

In simple terms, you need to maintain a string set $S$. There are several insertion operations; each insertion contains a string and a valid time interval (with a fixed length). You need to find, over all times, the maximum size of the string set $S$.

Input Format

The first line contains two integers $n, k$, representing the number of frames and the aging time (in minutes), respectively.

The next $n$ lines each contain two strings $s_1, s_2$, representing the source address contained in the frame and its arrival time. Here, $s_1$ is a MAC address consisting of $12$ hexadecimal digits, and $s_2$ has the format $a:b$, where $0 \le a \le 23$ and $0 \le b \le 59$. This means the frame arrives at the switch at hour $a$, minute $b$, and second $0$. If $a$ or $b$ is less than $10$, a leading zero is added.

Output Format

One line with one integer, representing the answer.

4 10
0123456789ABCDEF 00:10
0000000000ABCDEF 08:11
0123456789ABCDEF 00:15
0000000000ABCDEF 00:11

2

3 60
0123456789ABCDEF 13:00
0000000000000000 14:00
0123456789ABCDEF 12:30

1

见/example/switch/下的 switch1.in 

见/example/switch/下的 switch1.out

Hint

Sample Explanation

In sample $1$, at time $00:11$, there are $2$ source $\text{MAC}$ addresses in the table: $\text{0123456789ABC}$ and $\text{0000000000ABCDEF}$. Therefore, the required table size must be at least $2$, and it can be proven that this is the minimum required size.

Constraints

For all testdata, $1 \le n \le 10^5$ and $1 \le k \le 1440$.

For $50\%$ of the testdata, $1 \le n \le 500$.

Translated by ChatGPT 5