Note: The memory limit for this problem is 512MB, twice the default.
Bessie has taken on a new job as a train dispatcher! There are two train
stations: $A$ and $B$. Due to budget constraints, there is only a single track
connecting the stations. If a train departs a station at time $t$, then it will
arrive at the other station at time $t+T$ ($1\le T\le 10^{12}$).

There are $N$ ($1\le N\le 5000$) trains whose departure times need to 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}$). It is not permitted to have trains
going in opposite directions along the track at the same time (since they would
crash). However, it is permitted to have many trains on the track going in the
same direction at the same time (assume trains have negligible size).

Help Bessie schedule the departure times of all trains such that there are no
crashes and the total delay is minimized. If train $i$ is scheduled to leave at
time $a_i\ge t_i$, the total delay is defined as $\sum_{i=1}^N(a_i-t_i)$.

INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains $N$ and $T$.

Then $N$ lines follow, where the $i$th line contains the station $s_i$ and
time $t_i$ corresponding to the $i$th train.

OUTPUT FORMAT (print output to the terminal / stdout):
The minimum possible total delay over all valid schedules.

SAMPLE INPUT:
1 95
B 63
SAMPLE OUTPUT:
0

The only train leaves on time.
SAMPLE INPUT:
4 1
B 3
B 2
A 1
A 3
SAMPLE OUTPUT:
1

There are two optimal schedules. One option is to have trains $2,3,4$ leave on
time and train $1$ leave after a one-minute delay. Another is to have trains
$1,2,3$ leave on time and train $4$ leave after a one-minute delay.

SAMPLE INPUT:
4 10
A 1
B 2
A 3
A 21
SAMPLE OUTPUT:
13

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

SAMPLE INPUT:
8 125000000000
B 17108575619
B 57117098303
A 42515717584
B 26473500855
A 108514697534
B 110763448122
B 117731666682
A 29117227954
SAMPLE OUTPUT:
548047356974

SCORING:
Inputs 5-6: $N \le 15$Inputs 7-10: $N \le 100$Inputs 11-14: $N \le 500$Inputs 15-18: $N\le 2000$Inputs 19-24: No additional constraints

Problem credits: Brandon Wang

见题面

见题面