Monorail

Time limit2sMemory limit1024 MB

Summary

Schedule entry times for trains in both directions through a single-track tunnel so opposite trains never overlap, minimizing total waiting.

Level: Medium6 of 10
Topics: Dynamic programming, Greedy, Sorting
Solved: No attempts yet

Problem

You were about to start a long holiday in the south, but as usual the trains are delayed. This time a cargo train derailed in the Gotthard Base Tunnel through the Alps, and one of the two tubes was closed for several months. Luckily, after initial repairs, the other tube is open again for cargo traffic.

With only one track left, trains in the same direction can follow each other closely, but trains in opposite directions cannot pass each other. So a northbound train can enter only after all southbound trains have left the tunnel, and vice versa.

Today $n$ cargo trains want to pass through the tunnel. Each train arrives at one end at a given time and takes exactly $d$ minutes to cross the tunnel at a constant speed.

This is not your responsibility, but you decide to make a schedule for today's trains. For each train, you decide how long it waits at its entrance before entering. Your goal is to minimize the sum of waiting times at the entrance portals over all trains.

For simplicity, trains are short compared to the tunnel and are approximated as points moving along a line segment.

Input

The first line contains integers $n$ and $d$ ( $1 \leq n \leq 500$ , $1 \leq d \leq 10^9$ ), the number of cargo trains and the time in minutes each train needs to cross the tunnel.

Each of the next $n$ lines contains a character $s$ and an integer $t$ ( $s$ is N or S, $0 \leq t \leq 10^9$ ). $s$ tells whether the train starts at the north or south portal, and $t$ is the number of minutes after the start time when the train arrives.

Trains are sorted by arrival time. For equal arrival times, trains from the north are listed before trains from the south.

Output

Output the minimum sum of waiting times at the tunnel entrances over all trains, in minutes.

Examples4

Example 1
Input
```
3 5
N 0
S 4
N 8
```
Expected output
```
3
```
Example 2
Input
```
4 10
N 5
N 10
S 10
N 15
```
Expected output
```
15
```
Example 3
Input
```
4 10
S 0
N 10
N 10
S 20
```
Expected output
```
0
```
Example 4
Input
```
4 10
N 0
S 5
S 5
S 5
```
Expected output
```
15
```