题目描述

题目译自 USACO 2023 December Contest, Platinum Problem 3. Train Scheduling

Bessie 有了一份新工作：火车调度员！有两个火车站 $A$ 和 $B$。由于预算限制，这两个车站之间只有一条轨道。如果火车在时刻 $t$ 离开火车站，那么它会在时刻 $t+T$ 到达另一个火车站。

有 $N$ 趟火车的出发时间需要被安排。第 $i$ 趟火车必须在时刻 $t_i$ 或之后离开 $s_i$ 站。不允许火车同时在轨道上相向而行（因为它们会相撞）。然而，允许轨道上有许多火车同时向同一方向行驶（假设列车的大小可以忽略不计）。

请帮 Bessie 安排所有火车的出发时间，满足火车不会相撞，并且总晚点时间最小。如果火车 $i$ 计划在时刻 $a_i\ge t_i$ 出发，则总晚点时间定义为 $\sum_{i=1}^N (a_i-t_i)$。

输入格式

第一行包含两个整数 $N\ (1\le N\le 5000)$ 和 $T\ (1\le T\le 10^{12})$。

接下来 $N$ 行，第 $i$ 行表示第 $i$ 趟火车的始发站 $s_i\ (s_i\in\{\texttt{A},\texttt{B}\})$ 和预计出发时刻 $t_i\ (0\le t_i\le 10^{12})$。

输出格式

输出一行，表示对于所有合法调度方案，最小的总晚点时间。

1 95
B 63

0

唯一的一趟火车正点出发。

4 1
B 3
B 2
A 1
A 3

1

有两种最优的调度方案。第一种是让火车 $2,3,4$ 正点出发，火车 $1$ 晚点一分钟。另一种是让火车 $1,2,3$ 正点出发，火车 $4$ 晚点一分钟。

4 10
A 1
B 2
A 3
A 21

13

最优的调度方案是让火车 $1$ 和 $3$ 正点出发，火车 $2$ 在时刻 $13$ 出发，火车 $4$ 在时刻 $23$ 出发。总晚点时间为 $0+11+0+2=13$。

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

548047356974

数据范围与提示

• 测试点 $5\sim 6$：$N\le 15$
• 测试点 $7\sim 10$：$N\le 100$
• 测试点 $11\sim 14$：$N\le 500$
• 测试点 $15\sim 18$：$N\le 2000$
• 测试点 $19\sim 24$：无附加限制

Problem credits: Brandon Wang