题目背景

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

题目描述

Bessie 找到了一份行车调度的新工作。现在有两座火车站 $A$ 和 $B$，由于预算限制，只有一条单线铁道连接起车站 $A$ 和 $B$。如果一列列车在 $t$ 时刻离开其中一座火车站，它将在 $t+T$（$1 \le T \le 10^{12}$）时刻到达另一座火车站。

现在有 $N$（$1 \le N \le 5000$）列火车的出发时间需要安排。第 $i$ 列火车必须在 $t_i$ 时刻后从车站 $s_i$ 出发（$s_i\in \{A,B\}$，$0 \le t_i \le 10^{12}$）。在同一时刻不允许铁道上有相反方向的列车，否则它们会相撞。但是，假设火车有可以忽略的尺寸，在同一时刻，铁道上可以有许多相同方向的列车。

帮助 Bessie 安排每辆列车的出发时间，在不会相撞的前提下最小化总延误时间。假设第 $i$ 辆列车被安排在 $a_i$ 时刻出发，总延误为 $\sum\limits_{i=1}^n{a_i-t_i}$。

输入格式

第一行包含 $N$ 和 $T$。

接下来 $N$ 行，第 $i$ 行包含用于描述第 $i$ 辆列车的 $s_i,t_i$。

输出格式

输出合法安排中最小总延误时间。

1 95
B 63

0

4 1
B 3
B 2
A 1
A 3

1

4 10
A 1
B 2
A 3
A 21

13

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

548047356974

提示

样例解释 1

唯一的一辆列车准点出发。

样例解释 2

有两种最佳方案。第一种是让列车 $2,3,4$ 准点出发，列车 $1$ 延误一分钟后出发。第二种是让列车 $1,2,3$ 准点出发，列车 $4$ 延误一分钟后出发。

样例解释 3

最佳方案是让列车 $1,3$ 准点出发，列车 $2$ 在时刻 $13$ 出发，列车 $4$ 在时刻 $23$ 出发。总延误为 $0+11+0+2=13$。

测试点性质

• 测试点 $5-6$ 满足 $N \le 15$。
• 测试点 $7-10$ 满足 $N \le 100$。
• 测试点 $11-14$ 满足 $N \le 500$。
• 测试点 $15-18$ 满足 $N \le 2000$。
• 测试点 $19-24$ 没有额外限制。