QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100
[0]

# 8532. Train Scheduling

Statistics

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 (1T1012).

There are N (1N5000) trains whose departure times need to be scheduled. The ith train must leave station si at time ti or later (si{A,B},0ti1012). 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 aiti, the total delay is defined as Ni=1(aiti).

Input

The first line contains N and T.

Then N lines follow, where the ith line contains the station si and time ti corresponding to the ith train.

Output

The minimum possible total delay over all valid schedules.

Examples

Input 1

1 95
B 63

Output 1

0

The only train leaves on time.

Input 2

4 1
B 3
B 2
A 1
A 3

Output 2

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.

Input 3

4 10
A 1
B 2
A 3
A 21

Output 3

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.

Input 4

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

Output 4

548047356974

Scoring

  • Inputs 5-6: N15
  • Inputs 7-10: N100
  • Inputs 11-14: N500
  • Inputs 15-18: N2000
  • Inputs 19-24: No additional constraints

Problem credits: Brandon Wang