题目描述

今天共有 $n$ 列货运列车需要通过隧道。每列列车从隧道的北端或南端到达，并且穿过整条隧道都需要恰好 $d$ 分钟。

列车相对于隧道长度可以视为一个点，因此：

• 多列同方向列车可以在任意接近的时间依次进入隧道；
• 相反方向的列车不能在隧道内相遇；
• 只有当隧道内所有南向列车均已离开后，北向列车才可以进入，反之亦然。

你需要为每列列车安排进入隧道的时间。列车不能早于自己的到达时间进入隧道。

一列列车的等待时间等于它进入隧道的时间减去它到达入口的时间。请最小化所有列车等待时间之和。

输入格式

第一行包含两个整数 $n,d$，分别表示列车数量和每列列车穿过隧道所需的时间。

接下来 $n$ 行，每行包含一个字符 $s$ 和一个整数 $t$：

• $s$ 为 N 时，表示该列车从北端出发；
• $s$ 为 S 时，表示该列车从南端出发；
• $t$ 表示该列车在时刻 $t$ 到达隧道入口。

数据范围：

• $1\le n\le 500$；
• $1\le d\le 10^9$；
• $s\in\{\texttt{N},\texttt{S}\}$；
• $0\le t\le 10^9$。

输入中的列车已经按照到达时间非递减排列。若多列列车到达时间相同，则从北端出发的列车排在从南端出发的列车之前。

输出格式

输出一个整数，表示所有列车等待时间之和的最小值，单位为分钟。

样例 1

输入

3 5
N 0
S 4
N 8

输出

3

样例 2

输入

4 10
N 5
N 10
S 10
N 15

输出

15

样例 3

输入

4 10
S 0
N 10
N 10
S 20

输出

0

样例 4

输入

4 10
N 0
S 5
S 5
S 5

输出

15