Background

Note: The memory limit for this problem is 512MB, twice the default.

Problem Description

Bessie has found a new job in train scheduling. There are now two train stations, $A$ and $B$. Due to budget limits, there is only a single-track railway connecting station $A$ and station $B$. If a train leaves one of the stations at time $t$, it will arrive at the other station at time $t+T$ ($1 \le T \le 10^{12}$).

Now there are $N$ ($1 \le N \le 5000$) trains whose departure times need to be scheduled. Train $i$ must depart from station $s_i$ after time $t_i$ ($s_i\in \{A,B\}$, $0 \le t_i \le 10^{12}$). Trains traveling in opposite directions are not allowed to be on the track at the same time, or they will collide. However, assume trains have negligible size, so at the same time the track can contain many trains traveling in the same direction.

Help Bessie schedule the departure time for each train, minimizing the total delay while avoiding collisions. Suppose train $i$ is scheduled to depart at time $a_i$. The total delay is $\sum\limits_{i=1}^n{a_i-t_i}$.

Input Format

The first line contains $N$ and $T$.

The next $N$ lines each describe one train. Line $i$ contains $s_i, t_i$ for train $i$.

Output Format

Output the minimum total delay among all valid schedules.

1 95
B 63

0

4 1
B 3
B 2
A 1
A 3

1

4 10
A 1
B 2
A 3
A 21

13

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

548047356974

Hint

Sample Explanation 1

The only train departs on time.

Sample Explanation 2

There are two optimal schedules. In the first, trains $2,3,4$ depart on time, and train $1$ departs with a $1$-minute delay. In the second, trains $1,2,3$ depart on time, and train $4$ departs with a $1$-minute delay.

Sample Explanation 3

The optimal schedule is: trains $1,3$ depart on time, train $2$ departs at time $13$, and train $4$ departs at time $23$. The total delay is $0+11+0+2=13$.

Test Point Properties

• Test points $5-6$ satisfy $N \le 15$.
• Test points $7-10$ satisfy $N \le 100$.
• Test points $11-14$ satisfy $N \le 500$.
• Test points $15-18$ satisfy $N \le 2000$.
• Test points $19-24$ have no additional constraints.

Translated by ChatGPT 5