Single‐Track Railway Scheduling

Bessie has started a new job scheduling trains between two stations, A and B. Due to a limited budget, only a single‐track railway connects the two stations. When a train departs from one station at time \(t\), it will arrive at the other station at time \(t+T\), where \(1\le T\le10^{12}\).

There are \(N\ (1\le N\le 5000)\) trains that need to be scheduled, and the \(i\)th train is available for departure from its station \(s_i\) (either A or B) at time \(t_i\) (with \(0\le t_i\le10^{12}\)). In other words, the train cannot depart before time \(t_i\). Multiple trains going in the same direction are allowed on the track at the same time (their sizes are negligible). However, at any moment the track must not have trains traveling in opposite directions; otherwise a collision will occur.

Your task is to assign a departure time \(a_i\) for each train (with \(a_i\ge t_i\)) so that no collision occurs and the total delay \(\sum_{i=1}^{N} (a_i - t_i)\) is minimized.

The catch is that if trains from different stations use the track one after the other, the first train of the new block must depart no earlier than the moment when the previous block’s train has been on the track for \(T\) time (i.e. at least \(\text{last_departure}+T\)). For trains in the same block (coming from the same station consecutively), they can all depart simultaneously as long as they do not start before their available time. Formally, if several trains from the same station are grouped together in a block, you can choose a common departure time \(L\) (with \(L\ge \max(D, \max\{t_i\})\), where \(D\) is a lower bound imposed by a preceding block from the opposite station) and assign each train in that block a departure time of \(L\).

Your solution should compute the minimum total delay possible.

inputFormat

The first line contains two integers \(N\) and \(T\) — the number of trains and the travel time, respectively.

Each of the next \(N\) lines contains an integer \(t_i\) and a character \(s_i\) (either 'A' or 'B'), describing a train that can depart from station \(s_i\) at or after time \(t_i\).

outputFormat

Output a single integer — the minimum total delay over all trains.

sample

3 10
0 A
5 B
5 A

15