Moon is preparing for a computer networking exam and is reviewing knowledge about network switches. Switches have an amazing property: their tables are built automatically, dynamically, and autonomously, meaning there is no intervention from network administrators or configuration protocols. In other words, switches are self-learning. This capability is likely implemented as follows:

1) The switch table is initially empty. 2) For every data frame received on each interface, the switch stores the source MAC address of the data frame in its table. 3) If, after a certain period (called the aging period), the switch has not received a data frame containing a particular source MAC address, it deletes that source MAC address from the table.

Given all the data frames received by a switch on a certain day (each data frame contains a source MAC address and the arrival time of the data frame), please help Moon calculate the minimum number of entries the switch's table needs to store all the information for that day. Note that for simplicity, at each time point, the deletion operation is performed before the insertion operation.

Simply put, you need to maintain a set of strings $S$. There are several insertion operations, each containing a string and a valid time interval (the interval length is a constant). You need to find the maximum size of the set $S$ at any point in time.

Input

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

The next $n$ lines each contain two strings $s_1$ and $s_2$, representing the source MAC address of the data frame and its arrival time. $s_1$ is a MAC address containing 12 hexadecimal digits. The format of $s_2$ is $a:b$, where $0 \le a \le 23$ and $0 \le b \le 59$, indicating that the data frame arrived at the switch at $a$ hours and $b$ minutes and $0$ seconds. If $a$ or $b$ are less than 10, they are padded with a leading zero.

Output

A single integer representing the answer.

Examples

Input 1

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

Output 1

2

Input 2

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

Output 2

1

Note

In Example 1, at time 00:11, there are 2 source MAC addresses in the table: 0123456789ABCDEF and 0000000000ABCDEF. Therefore, the table size must be at least 2. It can be proven that this is the minimum required table size.

Constraints

For all data, $1 \le n \le 10^5$, $1 \le k \le 1440$. For 50% of the data, $1 \le n \le 500$.