Problem Background

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

Problem Description

Bessie has taken on a new job in train scheduling. There are two train stations, $A$ and $B$, connected by a single railway line due to budget constraints. If a train leaves one station at time $t$, 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 that need to have their departure times scheduled. The $i$-th train must depart from station $s_i$ ($s_i \in \{A, B\}$) after time $t_i$ ($0 \le t_i \le 10^{12}$). The railway cannot have trains in opposite directions at the same time, as they would collide. However, assuming trains have negligible size, multiple trains can be on the railway at the same time if they are all traveling in the same direction.

Help Bessie schedule the departure times of each train to minimize the total delay time without causing any collisions. If the $i$-th train is scheduled to depart at time $a_i$, the total delay is $\sum_{i=1}^n (a_i - t_i)$.

Input Format

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

The next $N$ lines each contain $s_i$ and $t_i$ describing the $i$-th train.

Output Format

Output the minimum total delay time in a valid schedule.

Sample Input and Output

Sample Input #1

1 95
B 63

Sample Output #1

0

Sample Input #2

4 1
B 3
B 2
A 1
A 3

Sample Output #2

1

Sample Input #3

4 10
A 1
B 2
A 3
A 21

Sample Output #3

13

Sample Input #4

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

Sample Output #4

548047356974

Notes

Sample Explanation 1

The only train departs on time.

Sample Explanation 2

There are two optimal solutions. The first is to have trains 2, 3, and 4 depart on time, and train 1 depart one minute late. The second is to have trains 1, 2, and 3 depart on time, and train 4 depart one minute late.

Sample Explanation 3

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

Test Case Properties

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

见题面 Input 部分

见题面 Output 部分