모노레일

당신은 남쪽으로 긴 휴가를 떠나려던 참이었지만, 늘 그렇듯 기차가 지연되고 있다. 이번에는 알프스를 관통하는 고타르트 기저 터널에서 화물열차 한 대가 탈선하여, 두 개의 터널 중 하나가 몇 달 동안 완전히 운행을 멈췄다. 다행히 초기 복구 후 나머지 터널은 다시 화물 운송에 쓸 수 있게 되었다.

이제 단선 구간이므로, 같은 방향으로 가는 열차들은 가까이 붙어서 연달아 달릴 수 있지만 반대 방향 열차끼리는 서로 지나갈 수 없다. 즉 북쪽으로 가는 열차는 남쪽으로 가는 열차가 모두 터널을 빠져나간 뒤에야 진입할 수 있고, 그 반대도 마찬가지다.

오늘 이 터널을 통과하려는 화물열차는 $n$대다. 각 열차는 주어진 시각에 양 끝 중 한쪽에 도착하며, 일정한 속도로 터널을 통과하는 데 정확히 $d$분이 걸린다.

이 일은 당신의 책임이 아니지만, 오늘 열차들의 운행 계획을 세우기로 한다. 각 열차마다 입구에서 진입하기 전에 얼마나 기다려야 하는지 정한다. 목표는 모든 열차의 입구 대기 시간 합을 최소화하는 것이다.

단순화를 위해 열차는 터널 길이에 비해 짧으며, 선분 위를 움직이는 점으로 근사한다고 가정한다.

첫 줄에 정수 $n$과 $d$가 주어진다 ($1 \leq n \leq 500$, $1 \leq d \leq 10^9$). $n$은 화물열차의 수이고, $d$는 각 열차가 터널을 통과하는 데 걸리는 시간(분)이다.

이후 $n$개의 줄에 문자 $s$와 정수 $t$가 주어진다 ($s$는 N 또는 S, $0 \leq t \leq 10^9$). $s$는 열차가 북쪽 입구에서 출발하는지 남쪽 입구에서 출발하는지를 나타내고, $t$는 시작 시각으로부터 열차가 도착하기까지 걸린 분이다.

열차는 도착 시각 순으로 정렬되어 있다. 도착 시각이 같으면 북쪽에서 오는 열차가 남쪽에서 오는 열차보다 먼저 나열된다.

모든 열차의 입구 대기 시간 합의 최솟값을 분 단위로 출력한다.