Dynamic MAC Address Aging Table

Moon is preparing for his computer networks exam and is studying switches. A switch builds its forwarding table automatically, dynamically, and autonomously with no network administrator intervention. In particular, the switch is self-learning. Its operation can be summarized as follows:

1. The switch table is initially empty.
2. For each frame received at any interface at time t with source \(\text{MAC}\) address, the switch records the source address and makes it valid for the interval \([t, t+T)\), where \(T\) is the aging period.
3. If during the aging period no frame with that source \(\text{MAC}\) address is received, the entry is removed from the table. Note: At every time point, deletions are performed first, followed by insertions.

In other words, one needs to maintain a set \(S\) of strings. Each insertion operation adds a string along with its valid time interval (of fixed length \(T\)). Your task is to compute the maximum size that \(S\) reaches throughout the day, which corresponds to the minimal number of entries needed in the switch table for all frames of the day to be stored.

inputFormat

The first line contains two integers \(n\) and \(T\), where \(n\) is the number of data frames and \(T\) is the aging period. Each of the next \(n\) lines contains an integer \(t\) and a string representing the source \(\text{MAC}\) address. The data frames are given in non-decreasing order of \(t\). Remember that at each time point, deletion occurs before insertion.

outputFormat

Output a single integer representing the maximum number of entries that are present in the switch's table at any time.

sample

3 3
1 A
2 B
5 A

2