题目描述

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

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

请帮 Bessie 安排所有火车的出发时间，满足火车不会相撞，并且总晚点时间最小。如果火车 i 计划在时刻 $a_i ≥ 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

数据规模与约定

测试点 $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：无附加限制