Bessie 找到了一份新工作，担任火车调度员！这里有两个火车站：$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\ge t_i$ 出发，则总延迟定义为 $\sum_{i=1}^N(a_i-t_i)$。

输入格式

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

接下来 $N$ 行，其中第 $i$ 行包含第 $i$ 列火车的出发车站 $s_i$ 和时间 $t_i$。

输出格式

所有有效调度方案中最小的总延迟。

样例

输入格式 1

1 95
B 63

输出格式 1

0

说明

唯一的一列火车准时出发。

输入格式 2

4 1
B 3
B 2
A 1
A 3

输出格式 2

1

说明

有两种最优调度方案。一种方案是让第 $2,3,4$ 列火车准时出发，第 $1$ 列火车延迟一分钟出发。另一种方案是让第 $1,2,3$ 列火车准时出发，第 $4$ 列火车延迟一分钟出发。

输入格式 3

4 10
A 1
B 2
A 3
A 21

输出格式 3

13

说明

最优调度方案是让第 $1$ 和第 $3$ 列火车准时出发，第 $2$ 列火车在时间 $13$ 出发，第 $4$ 列火车在时间 $23$ 出发。总延迟为 $0+11+0+2=13$。

输入格式 4

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

输出格式 4

548047356974

子任务

• 输入 5-6：$N \le 15$
• 输入 7-10：$N \le 100$
• 输入 11-14：$N \le 500$
• 输入 15-18：$N\le 2000$
• 输入 19-24：无额外限制