Train Scheduling

Time limit2sMemory limit1024 MB

Summary

Schedule N trains from two stations on one shared track so opposite-direction trains never overlap, minimizing the total delay past each train's earliest departure.

Level: Hard8 of 10
Topics: Sorting, Dynamic programming, Greedy
Solved: No attempts yet

Problem

Bessie has taken a new job as a train dispatcher. There are two stations, $A$ and $B$ . Because of budget limits, only one track connects them. If a train departs a station at time $t$ , it arrives at the other station at time $t+T$ ( $1\le T\le 10^{12}$ ).

There are $N$ trains ( $1\le N\le 5000$ ) whose departure times must be scheduled. The $i$ th train must leave station $s_i$ at time $t_i$ or later ( $s_i\in \{A, B\}$ , $0\le t_i\le 10^{12}$ ).

Trains going in opposite directions may not be on the track at the same time, because they would crash. Many trains may travel in the same direction at the same time. Assume trains have negligible size.

Input

The first line contains $N$ and $T$ . Each of the next $N$ lines contains the station $s_i$ and the time $t_i$ for the $i$ th train.

Output

Print the minimum possible total delay over all valid schedules. If train $i$ departs at time $a_i\ge t_i$ , the total delay is $\sum_{i=1}^N(a_i-t_i)$ .

Examples4

Example 1
Input
```
1 95
B 63
```
Expected output
```
0
```
Example 2
Input
```
4 1
B 3
B 2
A 1
A 3
```
Expected output
```
1
```
Example 3
Input
```
4 10
A 1
B 2
A 3
A 21
```
Expected output
```
13
```

Example 4

Input

8 125000000000
B 17108575619
B 57117098303
A 42515717584
B 26473500855
A 108514697534
B 110763448122
B 117731666682
A 29117227954

Expected output

548047356974